<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta property="og:type" content="website">
<meta property="og:title" content="Hexo">
<meta property="og:url" content="https://goofyer.gitee.io/notes-on-computer-expertise/page/14/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/notes-on-computer-expertise/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/notes-on-computer-expertise/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/notes-on-computer-expertise/css/style.css">

  
    
<link rel="stylesheet" href="/notes-on-computer-expertise/fancybox/jquery.fancybox.min.css">

  
<meta name="generator" content="Hexo 5.4.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/notes-on-computer-expertise/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/notes-on-computer-expertise/">Home</a>
        
          <a class="main-nav-link" href="/notes-on-computer-expertise/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/notes-on-computer-expertise/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://goofyer.gitee.io/notes-on-computer-expertise"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main">
  
    <article id="post-数据结构/数据结构作业" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BD%9C%E4%B8%9A/" class="article-date">
  <time class="dt-published" datetime="2021-12-15T13:34:55.000Z" itemprop="datePublished">2021-12-15</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BD%9C%E4%B8%9A/">数据结构作业</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="数据结构作业"><a href="#数据结构作业" class="headerlink" title="数据结构作业"></a>数据结构作业</h1><h1 id="第四章-树"><a href="#第四章-树" class="headerlink" title="第四章 树"></a>第四章 树</h1><h2 id="4-1"><a href="#4-1" class="headerlink" title="4.1"></a>4.1</h2><h3 id="一、图的定义"><a href="#一、图的定义" class="headerlink" title="一、图的定义"></a>一、图的定义</h3><ul>
<li>1.树最适合用来表示( )的数据。<ul>
<li>A.有序</li>
<li>B.无序</li>
<li>C.任意元素之间具有多种联系</li>
<li><strong>D.元素之间具有分支层次关系</strong><br>树是一种分层结构，它特别适合组织那些具有分支层次关系的数据。</li>
</ul>
</li>
<li><p>2.一棵有n个结点的树的所有结点的度数之和为( ).</p>
<ul>
<li><strong>A. n-1</strong></li>
<li>B. n</li>
<li>C. n+1</li>
<li>D.2n</li>
</ul>
</li>
<li><p>3.树的路径长度是从树根到每个结点的路径长度的( )。</p>
<ul>
<li><strong>A.总和</strong></li>
<li>B.最小值</li>
<li>C.最大值</li>
<li>D.平均值</li>
</ul>
</li>
<li><p>4.对于一棵具有n个结点、度为4的树来说，( )。</p>
<ul>
<li><strong>A.树的高度至多是n-3</strong></li>
<li>B.树的高度至多是n-4</li>
<li>C.第i层上至多有4(i- 1)个结点</li>
<li>D.至少在某一层上正好有4个结点</li>
</ul>
</li>
<li><p>5.度为4、高度为h的树，( ).</p>
<ul>
<li><strong>A. 至少有h+3个结点</strong></li>
<li>B.至多有4h-1个结点</li>
<li>C.至多有4h个结点</li>
<li>D.至少有h+4个结点</li>
</ul>
</li>
<li><p>6.假定一棵度为3的树中，结点数为50， 则其最小高度为( )。</p>
<ul>
<li>A. 3</li>
<li>B. 4</li>
<li><strong>C. 5</strong></li>
<li>D. 6</li>
</ul>
</li>
<li><ol>
<li>[2010统考真题]在一-棵度为4的树T中，若有20个度为4，10个度为3的结点，1个度为2的结点 10个度为1的结点，则树T的叶结点个数是。<ul>
<li>A.41</li>
<li><strong>B.82</strong></li>
<li>C.113</li>
<li>D.122</li>
</ul>
</li>
</ol>
</li>
</ul>
<h3 id="二、综合应用题"><a href="#二、综合应用题" class="headerlink" title="二、综合应用题"></a>二、综合应用题</h3><ul>
<li>1.含有n个结点的三叉树的最小高度是多少</li>
<li>2.已知一棵度为4的树中，度为0,1,2,3的结点数分别为14,4,3,2， 求该树的结点总数n和度为4的结点个数，并给出推导过程。</li>
<li><ol>
<li>已如一棵度为m的树中， 有n1个度为I 的结点， 有n2个度为2的结点有nm个度为m的结点，问该树有多少个叶子结点?</li>
</ol>
</li>
</ul>
<h2 id="4-3"><a href="#4-3" class="headerlink" title="4.3"></a>4.3</h2><p>1．在下列关于二叉树遍历的说法中,正确的是（)。<br>A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则他一定是该子树的前序遍历结果序列的最后一个节点<br>B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则他一定是该子树的中序遍历结果序列的最后一个结点<br>C.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个节点，则它</p>
<h1 id="第五章-图"><a href="#第五章-图" class="headerlink" title="第五章 图"></a>第五章 图</h1><h3 id="一、图的定义-1"><a href="#一、图的定义-1" class="headerlink" title="一、图的定义"></a>一、图的定义</h3><ul>
<li><p>单项选择题</p>
<ul>
<li><ol>
<li><p>图中有关路径的定义是( )。</p>
<ul>
<li>A.由顶点和相邻顶点序偶构成的边所形成的序列路径的定义</li>
<li>B.由不同顶点所形成的序列</li>
<li>C.有不同边所形成的序列</li>
<li>D.上述定义都不是</li>
</ul>
</li>
</ol>
</li>
<li><p>2.一个有n个顶点和n条边的无向图一定是</p>
<ul>
<li>A.连通的</li>
<li>C.无环的</li>
<li>B.不通通的</li>
<li><p>D.有环的</p>
<p>若在一个无向图有n个顶点和n-1个条边，可以使他们连通但没有环（生成树），但再加一条边</p>
</li>
</ul>
</li>
<li><p>3.若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是</p>
<ul>
<li><p>A.强连通图</p>
<p>强连通图是有向图，与题意矛盾</p>
</li>
<li><p>B. 连通图</p>
<p>对无向连通图做一次深度优先搜索，可以访问到该连通图的所有顶点</p>
</li>
<li><p>C有回路</p>
<p>有回路的无向图不一定是连通图，因为回路不一定包含所有节点</p>
</li>
<li><p>D.一棵树</p>
<p>连通图可能是树，也可能存在环</p>
</li>
</ul>
</li>
<li><p>4.下列关于图的叙述中，正确的是( ).</p>
<ul>
<li><p>Ⅰ 回路是简单路径</p>
<p>回路对应路径，简单回路对应简单路径</p>
</li>
<li><p>Ⅱ 存储稀疏图，用邻接矩阵比邻接表更省空间</p>
<p>稀疏图是边比较少的情况，此时用邻接矩阵必将浪费大量空间，应选用邻接表</p>
</li>
<li><p>Ⅲ 若有向图中存在招朴序列，则该图不存在回路</p>
<p>存在回路的图不存在拓扑序列</p>
</li>
</ul>
</li>
<li><p>5.以下关于图的叙述中，正确的是(</p>
<ul>
<li>A.图与树的区别在于图的边数大于等于顶点数</li>
<li>B.假设有图G={V,{E}}，顶点集V’∈V，E’∈E，则V’和{E’}构成G的子图</li>
<li>C无向图的连通分量是指无向图中的极大连通子图</li>
<li>D.图的通历就是从图中某一顶点出发访遍图中其余顶点</li>
</ul>
</li>
<li><p>6.下列关于无向连通图特性的叙述中，正确的是( ).</p>
<ul>
<li>Ⅰ所有顶点的度之和为偶数</li>
<li>Ⅱ边数大于顶点个数减1</li>
<li>Ⅲ 至少有一个顶点的度为1</li>
</ul>
</li>
<li><p>7.若无向图G=(V. E)中含有7个项点，要保证图G在任何情况下都是连通的，则需要的边数最少是( )。</p>
<ul>
<li>A.6</li>
<li>B.15</li>
<li>C.16</li>
<li>D.21</li>
</ul>
</li>
<li><ol>
<li><p>以下关于图的叙述中，正确的是( )。</p>
<ul>
<li>A.强连通有向图的任何顶点到其他所有顶点都有弧</li>
<li>B图的任意顶点的入度等于出度</li>
<li>C.有向完全图一定是强连通有向图</li>
<li>D有向图的边集的子集和顶点集的子集可构成原有向图的子图</li>
</ul>
</li>
</ol>
</li>
<li><p>10.一个伊欧28条边的非连通无向图至少有( )个顶点。</p>
<ul>
<li>A. 7</li>
<li>B. 8</li>
<li>C.9</li>
<li>D. 10</li>
</ul>
</li>
<li><p>11.对于一个有n个顶点的图:若是连通无向围，其边的个数至少为() </p>
<ul>
<li><p>若是强连通有向困，其边的个数至少为() .</p>
<ul>
<li>A.n-1,n</li>
<li>B. n-1,n(n-1)</li>
<li>C. n,n</li>
<li>D. n,n(n - 1)</li>
</ul>
</li>
</ul>
</li>
<li><p>12.无向图G有23条边，度为4的项点有5个，度为3的项点有4个。其余都是度为2的顶点，则图G最多有( )个顶点。</p>
<ul>
<li>A. 11</li>
<li>B. 12</li>
<li>C.15</li>
<li>D.16</li>
</ul>
</li>
<li><ol>
<li><p>在有n个顶点的有向图中，每个顶点的度最大可达( ).</p>
<ul>
<li>A. n</li>
<li>B. n-1</li>
<li>C.2n</li>
<li>D. 2n- 2</li>
</ul>
<p>在有向图中,顶点的度等于入度与出度之和，n个顶点的有向图中，任意一个顶点最多还可以与其他n-1个顶点有一对指向相反的边相连</p>
</li>
</ol>
</li>
<li><ol>
<li><p>具有6个顶点的无向图，当有( )条边时能确保是一个连通图。</p>
<ul>
<li>A.8</li>
<li>B.9</li>
<li>C.10</li>
<li>D. 11</li>
</ul>
</li>
</ol>
</li>
<li><ol>
<li><p>已知无向图G含有16条边，其中度为4的项点个数为3，度为3的顶点个数为4，其他顶点的度均小于3.图G所含的顶点个数至少是().</p>
<ul>
<li>A.10</li>
<li>B. 11</li>
<li>C.13</li>
<li>D.15</li>
</ul>
</li>
</ol>
</li>
<li><p>16.设有无向图G=(V,E)和G’=(V’,E’),若G’是G的生成树，则下列不正确的是().</p>
<ul>
<li><p>I. G’为G的连通分量</p>
<p>一个连通图的生成树是一个极小连通子图,显然它是无环的,故Ⅱ Ⅲ正确。极大连通子图称为连通分量，G’连通但非连通分量。这里冉补充一下极大连通子图:如果图本来就不是连通的,那么每个子部分若包含它本身的所有顶点和边,则它就是极大连通子图</p>
</li>
<li><p>II ,G”\为G的无环子图</p>
</li>
<li>|||. G’为G的极小连通子图且V=V’</li>
</ul>
</li>
<li><ol>
<li><p>若具有n个顶点的图是一个环，则它有( )棵生成树。</p>
<ul>
<li>A. n²</li>
<li>B. n</li>
<li>C.n-1</li>
<li>D. 1</li>
</ul>
</li>
</ol>
</li>
<li><ol>
<li><p>若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有()棵树。</p>
<ul>
<li>A. n</li>
<li>B. e</li>
<li>C. n-e</li>
<li>D.1</li>
</ul>
</li>
</ol>
</li>
</ul>
</li>
<li><p>二、综合应用题</p>
<ul>
<li><p>1.图G是一个非连通无向图， 共有28条边，该图至少有多少个顶点?</p>
<p>由于图G是一个非连通无向图，在边数固定时，顶点数最少的情况是该图由两个连通子图构成,且其中之一只含一个顶点，另一个为完全图,其中只含一个而占的子图沿有边，另一个完生<br>图的边数为n(n-1)/2=28,得n=8。所以该图至少有1+8=9个顶点。</p>
</li>
<li><p>如何对无环有向图中的顶点好重新安排可使该图的邻接矩阵中所有的I大批空壮 </p>
<p>按各顶点的出度进行排序。n个顶占的有向图甘顶占的是十出底具n_1，最小出度为0</p>
<p>排序以后出度最大的顶点编号为1 出度最小的顶点编号为n。之后调整，只要存在《i，j》 不断顶点j的出度是否大于顶点i的出度都把i编号在j之前，因为只有i≥j，<i,j>对应的1才能出现在邻孩矩阵的上三角</p>
</li>
</ul>
</li>
</ul>
<h3 id="二、图的存储结构和操作"><a href="#二、图的存储结构和操作" class="headerlink" title="二、图的存储结构和操作"></a>二、图的存储结构和操作</h3><ul>
<li><p>单项选择</p>
<ul>
<li>1.</li>
<li>2.</li>
<li>3.</li>
<li>4.</li>
<li>5.</li>
<li>6.</li>
<li>7.</li>
<li>8.</li>
<li>9.</li>
<li>10.</li>
<li>11.</li>
<li>12.</li>
<li>13.</li>
<li>14.</li>
<li>15.</li>
<li>16.</li>
</ul>
</li>
<li><p>综合应用题</p>
<ul>
<li>1.</li>
<li>2.</li>
<li>3.</li>
<li>4.</li>
<li><p>5.</p>
<ul>
<li>1)写出图G的邻接矩阵A(行、列下标从0开始)。</li>
<li></li>
<li><h1 id="第七章-排序"><a href="#第七章-排序" class="headerlink" title="第七章 排序"></a>第七章 排序</h1><h2 id="7-1"><a href="#7-1" class="headerlink" title="7.1"></a>7.1</h2><h3 id="一、单项选择题"><a href="#一、单项选择题" class="headerlink" title="一、单项选择题"></a>一、单项选择题</h3></li>
</ul>
</li>
</ul>
</li>
<li>1.下述排序方法中，不属于内部排序方法的是（).<ul>
<li>A.插入排序</li>
<li>B.选择排序</li>
<li><strong>C.拓扑排序</strong></li>
<li>D.冒泡排序</li>
</ul>
</li>
<li>2.排序算法的稳定性是指（)。<ul>
<li><strong>A,经过排序后，能使关键字相同的元素保持原顺序的相对位置不变</strong></li>
<li>B.经过排序后，能使关键字相同的元素保持原顺序的绝对位置不变</li>
<li>C.排序算法的性能与被排序元素个数关系不大</li>
<li>D.排序算法的性能与被排序元素的个数关系密切</li>
</ul>
</li>
<li>3.下列关于排序的叙述中,正确的是（)。<ul>
<li>A.稳定的排序方法优于不稳定的排序方法</li>
<li><strong>B.对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同</strong></li>
<li>C.排序方法都是在顺序表上实现，在练表上无法实现排序方法</li>
<li>D.在顺序表上实现的排序方法在链表上也可以实现</li>
</ul>
</li>
<li>4、对任意7个关键词进行基于比较的排序，至少要进行()次关键词之间的两两比较<ul>
<li><strong>A.13</strong></li>
<li>B.14</li>
<li>C.15</li>
<li>D.6</li>
</ul>
</li>
</ul>
<h2 id="7-2-4"><a href="#7-2-4" class="headerlink" title="7.2.4"></a>7.2.4</h2><h3 id="一、单项选择题-1"><a href="#一、单项选择题-1" class="headerlink" title="一、单项选择题"></a>一、单项选择题</h3><p>1.对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是()<br>A.8<br><strong>B.10</strong><br>C.15<br>D.25<br>2、在待排序的元素序列基本有序的前提 ，效率最高的排序方法是<br><strong>A.直接插入排序</strong><br>B.简单选择排序<br>C.快速排序<br>D.归并排序<br>3.【2O12统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序、两者之间可能的不同之处是（).<br>A．排序的总趟数<br>B.元素的移动次数<br>C.使用辅助空间的数量<br><strong>D.元素之间的比较次教</strong><br>4.、对有n个元素的顺序表采用直接插入排序算法进行排序，在最坏情况下所需的比较次数是( );在最好情况下所需的比较次数是().<br><strong>A. n-1</strong><br>B. n+l<br>C. n/2<br><strong>D. n(n-1)2</strong><br>5、数据序列{8.10,13,4,6,7,22,2,3}只能是()两趟排序后的结果。<br>A简单选择排序<br>B.起泡排序<strong>**
</strong>C.直接插入排序<strong><br>D.堆排序<br>6．用直接插入排序算法对下列4个表进行排序，比较次教最少的是().<br>A.94,32,40,90,80,46,21,69
</strong>B.21,32,46,40,80,69,90,94<strong><br>C.32,40,21,46,69,94,90,80<br>D. 90,69,80,46,21,32,94,40<br>7．在下列算法中,()算法可能出现下列情况、在最后一趟开始之前所有元素都不在最终位置上。<br>A.堆排序<br>B.冒池排序
</strong>C.直接插入排序<strong><br>D.快速排序<br>8．希尔排序属于（)。
</strong>A.插入排序<strong><br>B.交换排序<br>C.选择排序<br>D.归并排厅<br>9．对序列{150,9,7,8,20,-1,4}用希尔方法排序,经一趟后序列变为{15,-1,4,8,20,9,7}，则该次采用的增量是（)。<br>A.1
</strong>B.4**<br>C. 3<br>D.2</p>
<ol>
<li>【2009】用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9.1.4 13 7 8 20 23 15，则该趟排序采用的增量（间隔）可能是()。<br>A.2<br><strong>B.3</strong><br>C.4<br>D.5<br>11.若对于第9题中的序列，京一趟排序后序列变成{9.15.7.8, 20,-1,4}，则采用的是下列的（)。<br>A.选择排序<br>B.快速排序<br><strong>C.直接插入排序</strong><br>D.冒泡排序</li>
</ol>
<p>12.【2009统考真题】若数据元素序列{11.12.13.7.8.9.23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。<br>A.冒泡排序<br><strong>B.插入排序</strong><br>C.选择排序<br>D.2路归并排序<br>13.对序列{98,36,-9,0,47,23,1,8,10,7}采用希尔排序，下列序列()是增量为4的一趟排序结果。<br><strong>A. {10,7,-9,0,47, 23,1,8,98,36}</strong><br>B. {-9,0,36,98,1,8,23,47,7,10}<br>C. {36,98,-9,0,23,47,1,8,7,10}<br>D.以上都不对<br>14.折半插入排序算法的时间复杂度为（)。<br>A. O(n)<br>B.O(nlog2n)<br><strong>C. O(n2)</strong><br>D. O(n3)<br>15．有些排序算法在母趟排厅过在中，都会有一个元素被放置到其最终位置上，下列（)算法不会出现此种情况。<br><strong>A.希尔排序</strong><br>B．堆排序<br>C．冒泡排序<br>D.快速排序</p>
<ol>
<li>以下排序算法中，不稳定的是（)。<br>A．冒泡排序<br>B.直接插入排序<br><strong>C.希尔排序</strong><br>D.归并排序<br>17.以下排序算法中,稳定的是（)。<br>A．快速排序<br>B.堆排序<br><strong>C.直接插入排序</strong><br>D.简单选择排序<h3 id="二、综合应用题-1"><a href="#二、综合应用题-1" class="headerlink" title="二、综合应用题"></a>二、综合应用题</h3></li>
</ol>
<ul>
<li>1.给出关键字序列{4,5,1,2,6,3}的直接插入排序过程.<br>直接插入排序过程如下:<br>初始序列: 4,5,1,2,6,3<br>第一趟:<br>4.5,1,2.6,3<br>(将5插入{4})<br>第二趟:<br>1,4,5,2,6,3<br>(将1插入{4,5})<br>第三趟:<br>1.2,4,5,6,3<br>(将2插入{1,4,5})<br>第四趟:<br>1,2,4,5,6,3<br>(将6插入{1,2,4,5})<br>第五趟:<br>1,2,3,4,5,6<br>(将3插入{1,2,4,5.61）</li>
<li>2．给出关键字序列{50,26,38,80,70,90,8,30,40, 20}的希尔排序过程（取增量序列为d={5,3,1}，排序结果为从小到大排列).<br>原始序列:<br>50,26,38,80.70,90,8,30,40,20<br>第一趟(增量5):<br>50,8,30,40,20,90,26,38,80,70<br>第二趟(增量3):<br>26,8,30,40,20,80,50,38,90,70<br>第二趟(增量1):<br>8,20,26,30,38,40,50,70,80,90</li>
</ul>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BD%9C%E4%B8%9A/" data-id="cl403sxsa003mf8vugeaibl1y" data-title="数据结构作业" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-英语/英语" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/15/%E8%8B%B1%E8%AF%AD/%E8%8B%B1%E8%AF%AD/" class="article-date">
  <time class="dt-published" datetime="2021-12-15T13:34:55.000Z" itemprop="datePublished">2021-12-15</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E8%8B%B1%E8%AF%AD/">英语</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/15/%E8%8B%B1%E8%AF%AD/%E8%8B%B1%E8%AF%AD/">英语</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="英语"><a href="#英语" class="headerlink" title="英语"></a>英语</h1><h2 id="词根总结"><a href="#词根总结" class="headerlink" title="词根总结"></a>词根总结</h2><h3 id="表示-形容词后缀，加在动词或名词后面"><a href="#表示-形容词后缀，加在动词或名词后面" class="headerlink" title="表示  形容词后缀，加在动词或名词后面"></a>表示  形容词后缀，加在动词或名词后面</h3><p>例如:<br>considerate      体贴的，体谅的；深思熟虑；到；慎重；<br>fortunate      侥幸的，幸运的；带来幸运的，吉利的； 有好运的人；<br>passionate      热烈的；激昂的；易怒的；易被情欲所支配的；<br>collegiate      学院的，大学的；高校学生的；大学程度的；集体组织的；<br>moderate      有节制的；稳健的，温和的；适度的，中等的；&lt;美俚&gt;慢吞吞的； 使和缓；主持；节制； 变缓和；作主持人；<br>regenerate      回收（废热，废料等）；使再生；革新；使悔悟； 再生的；革新的；改过自新的；<br>inveterate      （指人）有恶习的，成瘾的；（指习惯等）根深蒂固的；痼；<br>innate      天生的；特有的，固有的；内在的，直觉的；<br>effeminate      （指男人）柔弱的，女人气的；<br>inanimate      无生命的；无生气的； 无精打采的； 单调的；<br>illegitimate      非婚生的，私生的；法律不容的；（指辩论等的结论）不合逻辑的； 非嫡出子；<br>表示  表动词，做，造成</p>
<p>例如:<br>differentiate      区分，区别，辨别； 区别对待； 表明…间的差别，构成…间差别的特征；[数学] 求…的微分：计算导<br>liquidate      清算；清偿；结束；换现款；<br>infiltrate      （使）渗透，（使）渗入；（使）潜入； 渗透物；<br>remonstrate      抗议； 告诫；<br>frustrate      挫败；阻挠；使受挫折； 无益的，无效的；<br>attenuate      （使）变细；（使）变薄；（使）变小；减弱； 稀薄的；细小的；减弱的；减少的；<br>表示  表名词，人或地位</p>
<p>例如:<br>graduate      渐变；渐渐变为（与into连用）；渐渐消逝（与away连用）；取 授予学位或毕业证书；从…接受学位；分成等级；标以刻度； &lt;美&gt;毕业生；&lt;英&gt;大学毕业生；（已经取得学士学位正在攻读高级学 &lt;美&gt;毕业了的，研究生的；有（学士）学位的；<br>delegate      代表，代表团成员； 委派代表；授权给；[法律]债务转移；<br>candidate      报考者；申请求职者；攻读学位者；最后命运或结局如何已显然可见者；<br>advocate      提倡；拥护；鼓吹；为…辩护； （辩护）律师；提倡者；支持者；<br>surrogate      代理，代表；代用品，代替，代孕者，[心]代用人物；〈美〉遗嘱检验 代理的；代理的； 代理，替代；<br>celibate      独身者； 独身者的；<br>reprobate      道德败坏的人，恶棍；<br>electorate      选民（全体）；选举区；[史]选帝侯的爵位[领土]；<br>doctorate      博士学位；博士头衔；</p>
<h3 id="分支主题-30"><a href="#分支主题-30" class="headerlink" title="分支主题 30"></a>分支主题 30</h3><h3 id="objectiveness"><a href="#objectiveness" class="headerlink" title="objectiveness"></a>objectiveness</h3><h3 id="ion"><a href="#ion" class="headerlink" title="-ion"></a>-ion</h3><ul>
<li><p>n   实际的东西</p>
<ul>
<li>production  产品</li>
<li>invention  n 发明物</li>
</ul>
</li>
</ul>
<h3 id="ity"><a href="#ity" class="headerlink" title="-ity"></a>-ity</h3><ul>
<li><p>n 抽象后缀  ……性</p>
<ul>
<li>productivity  生产力、生产率</li>
<li>objectivity</li>
<li><p>practicality</p>
<ul>
<li>n 可行性、实际情况</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="ize"><a href="#ize" class="headerlink" title="-ize"></a>-ize</h3><ul>
<li><p>v 使……</p>
<ul>
<li>publicize   使公开</li>
<li>customize  定制化</li>
<li>standardize 标准化</li>
<li><p>commercialized</p>
<ul>
<li>adj 商业化的</li>
</ul>
</li>
<li><p>democratize</p>
<ul>
<li>v 使民主化</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="ive"><a href="#ive" class="headerlink" title="-ive"></a>-ive</h3><ul>
<li><p>有……的能力</p>
<ul>
<li>productive   富有成效的、具有创造力的</li>
<li>conductive   传导性的</li>
</ul>
</li>
</ul>
<h3 id="ism"><a href="#ism" class="headerlink" title="-ism"></a>-ism</h3><ul>
<li><p>……主义</p>
<ul>
<li>consumerism  消费主义</li>
<li>intellectualism 智慧主义</li>
<li>子主题 3</li>
</ul>
</li>
</ul>
<h3 id="ist"><a href="#ist" class="headerlink" title="-ist"></a>-ist</h3><ul>
<li><p>……家</p>
<ul>
<li>environmentalist</li>
</ul>
</li>
</ul>
<h3 id="cogn"><a href="#cogn" class="headerlink" title="cogn"></a>cogn</h3><ul>
<li><p>认识</p>
<ul>
<li>recognize   v 识别</li>
</ul>
</li>
</ul>
<h3 id="sub"><a href="#sub" class="headerlink" title="sub"></a>sub</h3><ul>
<li><p>下</p>
<ul>
<li><p>subtitle</p>
<ul>
<li>n 小标题、字幕</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="out"><a href="#out" class="headerlink" title="out"></a>out</h3><ul>
<li><p>向外</p>
<ul>
<li>outweigh v 超过</li>
</ul>
</li>
</ul>
<h3 id="lect"><a href="#lect" class="headerlink" title="lect"></a>lect</h3><ul>
<li><p>选择</p>
<ul>
<li>intellect  n 智力</li>
</ul>
</li>
</ul>
<h3 id="en"><a href="#en" class="headerlink" title="en-"></a>en-</h3><ul>
<li><p>使动</p>
<ul>
<li>entitle   v叫做、给与权力资格</li>
</ul>
</li>
</ul>
<h3 id="sub-1"><a href="#sub-1" class="headerlink" title="sub-"></a>sub-</h3><ul>
<li><p>下</p>
<ul>
<li>subtitle   n 下标题 副标题</li>
</ul>
</li>
</ul>
<h3 id="able"><a href="#able" class="headerlink" title="able"></a>able</h3><ul>
<li>available 可利用的</li>
<li>obtainable  可得到的</li>
<li>accessable 可接近的、易得到的</li>
</ul>
<h3 id="duce"><a href="#duce" class="headerlink" title="duce"></a>duce</h3><ul>
<li>introductory   引言的</li>
</ul>
<h3 id="ly"><a href="#ly" class="headerlink" title="-ly"></a>-ly</h3><ul>
<li><p>n-&gt;  adj</p>
<ul>
<li>bodily 身体的</li>
</ul>
</li>
<li><p>adj-&gt; adv</p>
<ul>
<li>intelligently   adv 明智地</li>
</ul>
</li>
</ul>
<h3 id="sem、sym、sim-same"><a href="#sem、sym、sim-same" class="headerlink" title="sem、sym、sim=same"></a>sem、sym、sim=same</h3><ul>
<li><p>assemble</p>
<ul>
<li>v 使集合</li>
</ul>
</li>
<li><p>resemble</p>
</li>
<li><p>simultaneously</p>
<ul>
<li>sim=same</li>
</ul>
</li>
</ul>
<h3 id="un"><a href="#un" class="headerlink" title="un-"></a>un-</h3><ul>
<li><p>不 否定</p>
<ul>
<li>unconcerned 不关心的</li>
<li>unrecognized 未被认识的</li>
<li><p>unavoidable</p>
<ul>
<li>不可避免的</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="inter"><a href="#inter" class="headerlink" title="inter-"></a>inter-</h3><ul>
<li><p>互相</p>
<ul>
<li>interpret       v 解释、了解</li>
</ul>
</li>
</ul>
<h3 id="nov-new"><a href="#nov-new" class="headerlink" title="nov=new"></a>nov=new</h3><ul>
<li><p>新</p>
<ul>
<li><p>innovation</p>
<ul>
<li>创新</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="mis"><a href="#mis" class="headerlink" title="mis-"></a>mis-</h3><ul>
<li><p>感情色彩向下</p>
<ul>
<li>mislead 误导</li>
<li>misinterpret  v 曲解</li>
</ul>
</li>
</ul>
<h3 id="子主题-48"><a href="#子主题-48" class="headerlink" title="子主题 48"></a>子主题 48</h3><h3 id="前缀"><a href="#前缀" class="headerlink" title="前缀"></a>前缀</h3><ul>
<li><p>表示正负或增幅</p>
<ul>
<li><p>in- 否定</p>
<ul>
<li><p>inevitable</p>
<p>adj 不可避免的</p>
</li>
<li><p>independent</p>
<p>adj 独立自主的</p>
</li>
</ul>
</li>
<li><p>dis- 否定</p>
<ul>
<li><p>distrust </p>
<p>n/v 不信任</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>表示数量</p>
</li>
<li><p>表示位置关系</p>
<ul>
<li><p>out-外</p>
<ul>
<li><p>outcome</p>
<p>结果</p>
</li>
</ul>
</li>
<li><p>ex- 外</p>
<ul>
<li><p>expose</p>
<p>v 露出</p>
</li>
</ul>
</li>
<li><p>ob- 对面</p>
<ul>
<li>observe</li>
</ul>
</li>
<li><p>sup  suf sus</p>
<ul>
<li><p>向上</p>
<ul>
<li>sustanable</li>
</ul>
</li>
</ul>
</li>
<li><p>suc  sub</p>
<ul>
<li><p>向下</p>
<ul>
<li>succeed</li>
</ul>
</li>
</ul>
</li>
<li><p>de-</p>
<ul>
<li><p>=away</p>
<ul>
<li>denote  v 表示、代表</li>
<li><p>devoted</p>
<ul>
<li>adj 献身的</li>
</ul>
</li>
</ul>
</li>
<li><p>下</p>
<ul>
<li>depress</li>
</ul>
</li>
</ul>
</li>
<li><p>pro-  pri- pre- 向前的</p>
<ul>
<li>pro- </li>
<li>pri- </li>
<li><p>pre-</p>
<ul>
<li><p>预先、提前</p>
<ul>
<li><p>preconception</p>
<p>n 先见之明，成见</p>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>表示时间或次序</p>
</li>
<li>表示数字</li>
</ul>
<h3 id="后缀"><a href="#后缀" class="headerlink" title="后缀"></a>后缀</h3><ul>
<li><p>表示“人”的名词后缀</p>
<ul>
<li><p>-aire </p>
<ul>
<li><p>person who.that which …</p>
<ul>
<li>-的人或物</li>
</ul>
</li>
</ul>
</li>
<li><p>-ant </p>
<ul>
<li><p>having the quality of </p>
<ul>
<li>具有…性质的人或物</li>
</ul>
</li>
</ul>
</li>
<li><p>-ary,-ory </p>
<ul>
<li><p>person who</p>
<ul>
<li>…的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-ate </p>
<ul>
<li><p>person who.that whiche…</p>
<ul>
<li>的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-cian</p>
<ul>
<li><p>person who </p>
<ul>
<li>…的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-ee</p>
<ul>
<li><p>one who</p>
<ul>
<li>成为…的人,做…的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-ent </p>
<ul>
<li><p>person who, having the quality of </p>
<ul>
<li>…的人，带有…性质的</li>
</ul>
</li>
</ul>
</li>
<li><p>-ier </p>
<ul>
<li><p>person who</p>
<ul>
<li>…的人,与…相关的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-ist</p>
<ul>
<li><p>person who</p>
<ul>
<li>…的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-or.-our </p>
<ul>
<li><p>one who.that which</p>
<ul>
<li>…的人或物</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="后缀-1"><a href="#后缀-1" class="headerlink" title="后缀"></a>后缀</h3><ul>
<li><p>名词后缀</p>
<ul>
<li><p>表示人的名词后缀</p>
<ul>
<li><p>-aire </p>
<ul>
<li>person who that which ……的人或物</li>
</ul>
</li>
<li><p>-ant</p>
<ul>
<li><p>having the quality of </p>
<ul>
<li>具有……性质的人或物</li>
</ul>
</li>
</ul>
</li>
<li><p>—ary，-ory</p>
<ul>
<li><p>person who</p>
<ul>
<li>……的人</li>
</ul>
</li>
</ul>
</li>
<li><p>-ate</p>
<ul>
<li>person who that which……的人</li>
</ul>
</li>
<li><p>-cian </p>
<ul>
<li>person who ……的人</li>
</ul>
</li>
<li><p>-ee</p>
<ul>
<li>one who ……成为……的人，做……的人</li>
</ul>
</li>
<li><p>-ent</p>
<ul>
<li>person wh having the quality of ……的人，带有……的性质</li>
</ul>
</li>
<li><p>-ier</p>
<ul>
<li>person who ……的人，与……相关的人</li>
</ul>
</li>
<li><p>-ist</p>
<ul>
<li>person who ……的人</li>
</ul>
</li>
<li><p>-or -our</p>
<ul>
<li>one who that which ……的人或物</li>
</ul>
</li>
</ul>
</li>
<li><p>表抽象名词的后缀</p>
<ul>
<li><p>-ace </p>
<ul>
<li>表抽象名词或地点</li>
</ul>
</li>
<li><p>-ade</p>
<ul>
<li><p>act,result,collective</p>
<ul>
<li>行动;结果;集体的，共同的</li>
</ul>
</li>
</ul>
</li>
<li><p>-age</p>
<ul>
<li><p>that which</p>
<ul>
<li>状态;行为;集合;地点;位置;质量;物品等</li>
</ul>
</li>
</ul>
</li>
<li><p>-al</p>
<ul>
<li><p>state.quality, one who, that which</p>
<ul>
<li>状态或性质，即…的人或物</li>
</ul>
</li>
</ul>
</li>
<li><p>-ance,-ancy</p>
<ul>
<li><p>state, quality,act,that which</p>
<ul>
<li>状态;性质;行为</li>
</ul>
</li>
</ul>
</li>
<li><p>-cy </p>
<ul>
<li><p>state, quality</p>
<ul>
<li>表性质或状态</li>
</ul>
</li>
</ul>
</li>
<li><p>-dom</p>
<ul>
<li><p>state,quality,position,place where</p>
<ul>
<li>表状态;性质;位置</li>
</ul>
</li>
</ul>
</li>
<li><p>-hood,-head</p>
<ul>
<li><p>period,quality</p>
<ul>
<li>表示“时期;带有…的性质”</li>
</ul>
</li>
</ul>
</li>
<li><p>-ic(s)</p>
<ul>
<li><p>study，art, science，system</p>
<ul>
<li>学科;艺术;学术;体系</li>
</ul>
</li>
</ul>
</li>
<li><p>-ice,ise</p>
<ul>
<li><p>act,state</p>
<ul>
<li>行为;状态</li>
</ul>
</li>
</ul>
</li>
<li><p>-ing</p>
<ul>
<li><p>state,business,cause to</p>
<ul>
<li>…的状态;行业;正…的;令人…的</li>
</ul>
</li>
</ul>
</li>
<li><p>-ion</p>
<ul>
<li><p>that which</p>
<ul>
<li>…的动作或状态(变形为-tion. -sion, -ation)</li>
</ul>
</li>
</ul>
</li>
<li><p>-ism,-asm</p>
<ul>
<li><p>belief，speech，condition,state,act</p>
<ul>
<li>信仰;主义;讲话;状况，状态;行为</li>
</ul>
</li>
</ul>
</li>
<li><p>-itude</p>
<ul>
<li><p>Oquality,state</p>
<ul>
<li>性质;状态</li>
</ul>
</li>
</ul>
</li>
<li><p>-ment</p>
<ul>
<li><p>state, quality,act,that which</p>
<ul>
<li>状态;性质;行为;…的物</li>
</ul>
</li>
</ul>
</li>
<li><p>-mony</p>
<ul>
<li><p>state</p>
<ul>
<li>状态</li>
</ul>
</li>
</ul>
</li>
<li><p>-ness</p>
<ul>
<li><p>state, quality</p>
<ul>
<li>状态;性质,通常加在形容词后面</li>
</ul>
</li>
</ul>
</li>
<li><p>-o(u)r</p>
<ul>
<li><p>one who,that whiche</p>
<ul>
<li>…的人或物</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>动词后缀</p>
</li>
<li>形容词后缀</li>
<li><p>-ly</p>
<ul>
<li>n+ly=&gt;adj</li>
<li>adj+ly=&gt;adv</li>
</ul>
</li>
</ul>
<h3 id="子主题-50"><a href="#子主题-50" class="headerlink" title="子主题 50"></a>子主题 50</h3><h3 id="mob-mot"><a href="#mob-mot" class="headerlink" title="mob  mot"></a>mob  mot</h3><ul>
<li><p>动</p>
<ul>
<li>mobile</li>
</ul>
</li>
</ul>
<h3 id="with"><a href="#with" class="headerlink" title="with-"></a>with-</h3><ul>
<li><p>后退】返回(同re-)</p>
<ul>
<li>withhold  扣留、拒绝给予</li>
<li>withstand  忍受</li>
</ul>
</li>
</ul>
<h3 id="pose"><a href="#pose" class="headerlink" title="pose-"></a>pose-</h3><ul>
<li><p>=put 放</p>
<ul>
<li><p>expose</p>
<ul>
<li>v 露出</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="ply"><a href="#ply" class="headerlink" title="-ply"></a>-ply</h3><ul>
<li><p>补充</p>
<ul>
<li>supply</li>
<li><p>supplyment </p>
<ul>
<li>补充物</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="ac"><a href="#ac" class="headerlink" title="ac-"></a>ac-</h3><ul>
<li><p>表加强</p>
<ul>
<li>account</li>
</ul>
</li>
</ul>
<h3 id="greg"><a href="#greg" class="headerlink" title="-greg-"></a>-greg-</h3><ul>
<li><p>聚集</p>
<ul>
<li><p>congregate</p>
<ul>
<li>v 聚集</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="ad-双写辅音"><a href="#ad-双写辅音" class="headerlink" title="ad-  双写辅音"></a>ad-  双写辅音</h3><ul>
<li><p>=to</p>
<ul>
<li><p>addict</p>
<ul>
<li><p>n 瘾君子</p>
<ul>
<li><p>addictive</p>
<ul>
<li>n\a</li>
</ul>
</li>
</ul>
</li>
<li><p>v 使沉溺</p>
<ul>
<li>be addicted to</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="river"><a href="#river" class="headerlink" title="river"></a>river</h3><ul>
<li><p>thrive</p>
<ul>
<li>v 欣欣向荣</li>
</ul>
</li>
</ul>
<h3 id="para"><a href="#para" class="headerlink" title="para"></a>para</h3><ul>
<li><p>不可分割</p>
<ul>
<li><p>parallel</p>
<ul>
<li>n 平行线、类似</li>
<li>adj 平行的、相同的</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="园"><a href="#园" class="headerlink" title="园"></a>园</h3><ul>
<li><p>circumstance</p>
<ul>
<li>n 情况</li>
</ul>
</li>
</ul>
<h3 id="cogn-1"><a href="#cogn-1" class="headerlink" title="cogn"></a>cogn</h3><ul>
<li><p>识别</p>
<ul>
<li><p>cognition</p>
<ul>
<li>n 识别</li>
</ul>
</li>
<li><p>regcognize</p>
<ul>
<li>v 认出、识别</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="de"><a href="#de" class="headerlink" title="de"></a>de</h3><ul>
<li><p>away</p>
<ul>
<li><p>decompose</p>
<ul>
<li>v 分解</li>
</ul>
</li>
<li><p>dilate</p>
<ul>
<li>v 稀释</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="介词时刻"><a href="#介词时刻" class="headerlink" title="介词时刻"></a>介词时刻</h2><h3 id="to"><a href="#to" class="headerlink" title="to"></a>to</h3><ul>
<li><p>服从于，听你的，你说了算</p>
<ul>
<li>defer to</li>
<li>contribute to</li>
<li>lead to</li>
<li>give rise to</li>
</ul>
</li>
<li><p>toward</p>
<ul>
<li><p>gear toward</p>
<ul>
<li>to gear lesson toward things they are interested in</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="as"><a href="#as" class="headerlink" title="as"></a>as</h3><ul>
<li>be define as</li>
<li>as a classic proverb goes,””</li>
</ul>
<h3 id="up"><a href="#up" class="headerlink" title="up"></a>up</h3><ul>
<li>向上</li>
</ul>
<h3 id="with-1"><a href="#with-1" class="headerlink" title="with"></a>with</h3><ul>
<li><p>和……在一起</p>
<ul>
<li>identify with    认同、与……有同感</li>
<li>integrate with   与……结合在一起</li>
<li><p>incorporate with</p>
<ul>
<li>合并、混合</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="from"><a href="#from" class="headerlink" title="from"></a>from</h3><ul>
<li><p>从……</p>
<ul>
<li>emerge from  从……出现、暴露</li>
</ul>
</li>
</ul>
<h3 id="分支主题-5"><a href="#分支主题-5" class="headerlink" title="分支主题 5"></a>分支主题 5</h3><h2 id="完型"><a href="#完型" class="headerlink" title="完型"></a>完型</h2><h3 id="一、公平公正原则-2-5"><a href="#一、公平公正原则-2-5" class="headerlink" title="一、公平公正原则(2.5)"></a>一、公平公正原则(2.5)</h3><ul>
<li>ABCD 98%的年份平均分配</li>
<li>英语一最后涂A</li>
<li>没有连续3个选项的答案是相同的</li>
<li>连着5个连续选项至少3个不同结果</li>
</ul>
<h3 id="二、优先筛选原则—-虚问题"><a href="#二、优先筛选原则—-虚问题" class="headerlink" title="二、优先筛选原则—-虚问题"></a>二、优先筛选原则—-虚问题</h3><ul>
<li><p>第一梯队</p>
<ul>
<li>除非明显不对，否则秒选</li>
<li><p>因为</p>
<ul>
<li>while</li>
<li>Because</li>
</ul>
</li>
<li><p>但是</p>
<ul>
<li>although</li>
</ul>
</li>
<li><p>however</p>
</li>
<li>yet</li>
<li>举例的词</li>
</ul>
</li>
<li><p>逃兵词</p>
<ul>
<li><p>since</p>
<ul>
<li><p>自从</p>
<ul>
<li>一定错</li>
<li>ever sincere</li>
</ul>
</li>
<li><p>因为</p>
<ul>
<li>不知道</li>
</ul>
</li>
</ul>
</li>
<li><p>now that</p>
<ul>
<li><p>既然</p>
<ul>
<li>一定错</li>
</ul>
</li>
</ul>
</li>
<li><p>unless</p>
<ul>
<li><p>除非</p>
<ul>
<li>错</li>
</ul>
</li>
</ul>
</li>
<li><p>instead</p>
<ul>
<li>句首一定错</li>
<li>句尾不知道</li>
</ul>
</li>
<li><p>关于一定错</p>
<ul>
<li>about</li>
<li>as to</li>
<li>as for</li>
<li>with/in reference to</li>
<li>with respect to</li>
<li>with regard to</li>
</ul>
</li>
<li><p>if only</p>
<ul>
<li>如果 会变好</li>
</ul>
</li>
<li><p>以防万一  一定错</p>
<ul>
<li>lest</li>
<li>for fear </li>
<li>in case</li>
</ul>
</li>
<li><p>except</p>
</li>
</ul>
</li>
</ul>
<h3 id="三、优先筛选原则—实问题"><a href="#三、优先筛选原则—实问题" class="headerlink" title="三、优先筛选原则—实问题"></a>三、优先筛选原则—实问题</h3><ul>
<li>Suggest</li>
<li>Consequence</li>
<li>Result</li>
<li>Link</li>
<li>Subject</li>
<li>Tend</li>
<li>Account</li>
<li>Produce</li>
<li>Generate</li>
<li>Show</li>
<li>influence</li>
<li>expose to</li>
<li>lead to</li>
<li>turn out</li>
<li>connect</li>
<li>predict</li>
<li>explain</li>
</ul>
<h3 id="四、反义原则"><a href="#四、反义原则" class="headerlink" title="四、反义原则"></a>四、反义原则</h3><ul>
<li>四个选择中有2个选项互为反义，答案一定在其中</li>
</ul>
<h3 id="五、所有介词题"><a href="#五、所有介词题" class="headerlink" title="五、所有介词题"></a>五、所有介词题</h3><ul>
<li>只需读介词所在的话</li>
</ul>
<h3 id="六、做所有逻辑关系词"><a href="#六、做所有逻辑关系词" class="headerlink" title="六、做所有逻辑关系词"></a>六、做所有逻辑关系词</h3><ul>
<li>对比关系 </li>
</ul>
<h2 id="作文"><a href="#作文" class="headerlink" title="作文"></a>作文</h2><h3 id="写作体型"><a href="#写作体型" class="headerlink" title="写作体型"></a>写作体型</h3><ul>
<li><p>题型</p>
<ul>
<li><p>小作文</p>
<ul>
<li>图画作文</li>
<li>图标</li>
</ul>
</li>
<li><p>大作文</p>
<ul>
<li>公务书信</li>
<li>私人书信</li>
<li>告示</li>
</ul>
</li>
</ul>
</li>
<li><p>方法</p>
<ul>
<li><p>书写工整</p>
<ul>
<li>单词正确</li>
<li>语法正确</li>
<li>三段论</li>
</ul>
</li>
<li><p>卷面整洁</p>
</li>
<li>字迹清晰</li>
</ul>
</li>
</ul>
<h3 id="写作满分句子"><a href="#写作满分句子" class="headerlink" title="写作满分句子"></a>写作满分句子</h3><ul>
<li><p>简单句</p>
<ul>
<li><p>被动</p>
<ul>
<li><p>parent should be respected by us</p>
<ul>
<li><p>parent</p>
<ul>
<li>superiors</li>
<li>the olderly</li>
<li>senior citizens</li>
</ul>
</li>
<li><p>should</p>
<ul>
<li>ought to</li>
<li>be supposed to</li>
<li>be obliged to</li>
</ul>
</li>
<li><p>we us people</p>
<ul>
<li>humanbeings</li>
<li>the public</li>
<li>private individuals</li>
<li>teenagers and young others</li>
<li>undergranduates</li>
<li>toungsters on compus</li>
<li>offspring</li>
<li>businessmen</li>
<li>experts and professors</li>
<li>all children and adults</li>
<li>men and women</li>
</ul>
</li>
</ul>
</li>
<li><p>celebrities ought not to be pursued by teenager and young others </p>
<ul>
<li><p>not</p>
<ul>
<li>never </li>
<li>by no mean</li>
<li>fail to</li>
</ul>
</li>
</ul>
</li>
<li><p>environmental contamination is thought very serious by an in inereasing amout of experts and professors</p>
<ul>
<li><p>think</p>
<ul>
<li>presume</li>
<li>argue</li>
</ul>
</li>
<li><p>very</p>
<ul>
<li>outstandingly </li>
<li>exceedingly</li>
<li>remarkably</li>
</ul>
</li>
<li><p>serious</p>
<ul>
<li>grave</li>
<li>fearful</li>
<li>be of great severity</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>并列句</p>
</li>
<li><p>and</p>
<ul>
<li>similarly</li>
<li>at the same time</li>
</ul>
</li>
<li><p>but</p>
<ul>
<li>nevertheless</li>
<li>on the contrary</li>
</ul>
</li>
</ul>
</li>
<li><ul>
<li><p>there seem句型</p>
<ul>
<li>适合第二段第一句 引出文章中心</li>
<li><p>there seem many reason to explain my idea</p>
<ul>
<li><p>many</p>
<ul>
<li>a sea of</li>
<li>immense amouts of</li>
</ul>
</li>
<li><p>reson</p>
<ul>
<li>cause </li>
<li>element</li>
<li>factor</li>
</ul>
</li>
<li><p>explain</p>
<ul>
<li>account for</li>
<li>get rise to导致</li>
</ul>
</li>
<li><p>idea</p>
<ul>
<li>viewpoint</li>
<li>outlook</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>比较结构</p>
<ul>
<li><p>as……as……</p>
<ul>
<li>推荐第一段末尾 第三段手段</li>
<li><p>she is as beautiful as red rose,which manages to take away the breath of a see of people.</p>
<ul>
<li><p>be</p>
<ul>
<li>look taste feel seem appear</li>
<li>keep remain</li>
<li>become get</li>
<li>prove</li>
</ul>
</li>
<li><p>beautiful</p>
<ul>
<li>graceful</li>
<li>elegant\</li>
<li>attractive</li>
<li>charming</li>
</ul>
</li>
</ul>
</li>
<li><p>confidence keep as import as sunshine,which plays an essential role in the normal grath of all creatures.</p>
<ul>
<li><p>important</p>
<ul>
<li>vital </li>
<li>significant</li>
<li>play a key role in sth</li>
<li>be of great importance</li>
</ul>
</li>
</ul>
</li>
<li><p>sth become as grave as AIDS,which has threatened the health of patients or taken away.</p>
</li>
</ul>
</li>
<li><p>the more the more</p>
<ul>
<li>推荐第二段 分析原因</li>
<li>the higher one ascends,the farther be will overlook</li>
<li>the more diligent one keeps,the more easiky be will achieve glories</li>
<li>the more diligent the public remain,the more fortunate they will become.</li>
<li>the more frequently the culture exchange the more rapidly chinese economy will develop.</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>复合句</p>
<ul>
<li><p>主语从句</p>
<ul>
<li><p>it……that……</p>
<ul>
<li>引出主题</li>
</ul>
</li>
<li><p>it keeps my perspective that=i think that</p>
</li>
<li>it seems beyond dispute that</li>
<li>what that+is</li>
</ul>
</li>
<li><p>同位语从句</p>
<ul>
<li>第二段分析原因</li>
<li><p>模板</p>
<ul>
<li>the evidence that 一个原因的简单句 manifest that 中心句</li>
</ul>
</li>
<li><p>my boyfriend,amch businessmen,really have no much time to accompany me,an attractive girl</p>
</li>
<li>a man,a soccerfan,is writing the name of Beckhom on his face</li>
<li>the evidence that she has a pair of bigeges manifests that she keeps a beauty</li>
</ul>
</li>
<li><p>定语从句</p>
<ul>
<li><p>定语</p>
<ul>
<li>名词后 谓语前</li>
<li><p>如何识别定语</p>
<ul>
<li>名词后的一坨东西，不是动词，暂定为修饰这个名词的定语成分</li>
</ul>
</li>
<li><p>定语翻译方法</p>
<ul>
<li><p>前置</p>
<ul>
<li>当定语成分简单信息量不大的时候，把定语翻译在名词前</li>
</ul>
</li>
<li><p>后置 </p>
<ul>
<li><p>当定语成分复杂信息量大的时候，把定语翻译在名词后，这需要重复先行词或则使用代词</p>
<ul>
<li><p>代词指代</p>
<ul>
<li>如果把代词仍能翻译成代词能表达清楚 可以使用代词，否则必须找出代词指代的内容</li>
<li>找内容，就近原则、一致原则（语法、意思）</li>
<li>如果找不到指代内容或不会表达，把代词翻译成这那</li>
</ul>
</li>
<li><p>专有名词</p>
<ul>
<li>根据习惯翻译</li>
<li>音译</li>
<li>如果专有名词翻译不来，允许写英文</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>区分when引导的定从</p>
<ul>
<li><p>看when前面的肩担此，是一个表时间名词的是定从，when翻译成当时这时 否则是庄从翻译成当……时</p>
<ul>
<li>i will never for the day when i meet you</li>
<li>i would forget you when i meet you</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>从句</p>
<ul>
<li>子主题 1</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="子主题-4"><a href="#子主题-4" class="headerlink" title="子主题 4"></a>子主题 4</h3><h3 id="子主题-19"><a href="#子主题-19" class="headerlink" title="子主题 19"></a>子主题 19</h3><h3 id="小作文"><a href="#小作文" class="headerlink" title="小作文"></a>小作文</h3><ul>
<li><p>公务书信</p>
<ul>
<li><p>称呼</p>
<ul>
<li><p>文章已给出</p>
<ul>
<li>Dear XXX</li>
</ul>
</li>
<li><p>文章没给出</p>
<ul>
<li>Dear Sir or Madam</li>
</ul>
</li>
</ul>
</li>
<li><p>第一段</p>
<ul>
<li><p>自我介绍</p>
<ul>
<li><p>文章已给出</p>
<ul>
<li>I am +</li>
</ul>
</li>
<li><p>I am senior who majors in computer science in this/a university.</p>
</li>
</ul>
</li>
<li><p>写作目的</p>
<ul>
<li>the reason why I am writing the letter,to be honest,is in order to <strong><strong><strong><strong>__</strong></strong></strong></strong></li>
</ul>
</li>
</ul>
</li>
<li><p>第二段</p>
<ul>
<li>it,to begin with,seems my argument that not only ……but also……</li>
<li>Then more importantly,so that</li>
<li>Another element i must point out here is that 简单句,which has been ignored by numerous 人.</li>
</ul>
</li>
<li><p>第三段</p>
<ul>
<li>so it is the very moment for me to do sth（文章目的）,and i am looking forward to you reply</li>
</ul>
</li>
<li><p>2019</p>
<ul>
<li>Dear volunteer,</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>I am senior who majors in computer science in this university.The reason why I am writing the letter,to be honest,is in order to show you the details of the project.</p>
<p>It,to begin with,seems my argument that this project is mainly to develop the English skills of rural children.</p>
<p>It is the world’s primary language. If the rural children can learn English well, rural children can improve their own foreign language level.Another element I must point out here is that this project can improve their competitiveness,which could be accepted by almost every all children and adults.So it is the very moment for me to carry into this project,and I am looking forward to your reply.</p>
<ul>
<li><p>私人书信</p>
<ul>
<li><p>称谓</p>
<ul>
<li><p>文中已给出</p>
<ul>
<li>Dear XXX</li>
</ul>
</li>
</ul>
</li>
<li><p>第一段</p>
<ul>
<li><p>问候语</p>
<ul>
<li>How are you getting along these days?I miss you very much</li>
</ul>
</li>
<li><p>写作目的</p>
<ul>
<li>the reason why I am writing the letter,to be honest,is in order to <strong><strong><strong><strong>__</strong></strong></strong></strong></li>
</ul>
</li>
</ul>
</li>
<li><p>第二段</p>
<ul>
<li>同上</li>
</ul>
</li>
<li><p>第三段</p>
<ul>
<li>Please accept my most sincere congratulations and I am looking forward to yours reply. </li>
</ul>
</li>
<li><p>yours truly，LiMing</p>
</li>
</ul>
</li>
<li><p>告示</p>
<ul>
<li>Welcome to English Club! It could serve as a platform to show your outstanding abilities and help you develop a range of great skills.</li>
<li>You can write a application to email us xxxxx@163.com. The deadline for entries is December 26. Come on, join us now!</li>
<li>English Club</li>
</ul>
</li>
<li><p>备忘录</p>
<ul>
<li>to：抄</li>
<li>from：抄</li>
<li>subject：抄</li>
<li>date：编</li>
<li><p>第一段</p>
<ul>
<li>具体活动</li>
<li>活动时间地点</li>
</ul>
</li>
<li><p>第二段</p>
<ul>
<li>同上</li>
</ul>
</li>
<li><p>第三段</p>
<ul>
<li>再次确认时间地点</li>
<li>要求人参加</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="大作文"><a href="#大作文" class="headerlink" title="大作文"></a>大作文</h3><ul>
<li><p>押题</p>
<ul>
<li><p>人生哲理</p>
<ul>
<li><p>合作</p>
<ul>
<li>teamwork</li>
<li>cooperation</li>
</ul>
</li>
<li><p>挫折、失败</p>
<ul>
<li>adversity</li>
<li>frustration</li>
<li>failure</li>
<li>difficulties</li>
<li>challenge</li>
<li>stress</li>
</ul>
</li>
<li><p>快乐</p>
<ul>
<li>happiness</li>
<li>satisfaction</li>
</ul>
</li>
<li><p>心态</p>
<ul>
<li>mentality</li>
</ul>
</li>
<li><p>诚信</p>
<ul>
<li>integrity</li>
<li>honesty</li>
</ul>
</li>
<li><p>信任危机</p>
<ul>
<li>crisis of faith</li>
<li>trust crisis</li>
</ul>
</li>
<li><p>谦虚</p>
<ul>
<li>friendship</li>
<li>diligence endeavor</li>
</ul>
</li>
</ul>
</li>
<li><p>社会热点</p>
<ul>
<li><p>污染</p>
<ul>
<li>environmental contamination</li>
</ul>
</li>
<li><p>交通</p>
<ul>
<li>traffic jam</li>
<li>private car</li>
</ul>
</li>
<li><p>酒驾</p>
<ul>
<li>drunken driving</li>
<li>awareness ifsecurity</li>
</ul>
</li>
<li><p>社会保障</p>
<ul>
<li>social security</li>
<li>medical care</li>
</ul>
</li>
<li><p>网络</p>
<ul>
<li><p>上网</p>
<ul>
<li>surfing on the Internet</li>
</ul>
</li>
<li><p>垃圾短信</p>
<ul>
<li>junk message</li>
</ul>
</li>
<li><p>虚拟社会</p>
<ul>
<li>virtual life</li>
</ul>
</li>
</ul>
</li>
<li><p>知识</p>
<ul>
<li>knowledge</li>
</ul>
</li>
<li><p>社会公德 </p>
<ul>
<li>social moral/ethics</li>
</ul>
</li>
<li><p>不良行为</p>
<ul>
<li>undesirable action</li>
</ul>
</li>
<li><p>献爱心</p>
<ul>
<li>show your loving heart</li>
</ul>
</li>
<li><p>健身热</p>
<ul>
<li>exercise</li>
<li>keep fit</li>
</ul>
</li>
<li><p>老龄化</p>
<ul>
<li>the aging problem</li>
</ul>
</li>
<li><p>垃圾分类</p>
<ul>
<li>garbage classification</li>
</ul>
</li>
<li><p>economy practice thrift</p>
</li>
<li>false advertisement </li>
<li><p>虚假产品</p>
<ul>
<li>fake products</li>
<li>authentic products</li>
</ul>
</li>
</ul>
</li>
<li><p>文化教育</p>
<ul>
<li><p>保护传统文化</p>
<ul>
<li>secure protect</li>
</ul>
</li>
<li><p>孩子教育</p>
<ul>
<li>children education</li>
</ul>
</li>
<li><p>自立</p>
<ul>
<li>self-dependence</li>
</ul>
</li>
<li><p>心理健康</p>
<ul>
<li>mental health </li>
<li>mental fitness</li>
</ul>
</li>
</ul>
</li>
<li><p>科技</p>
<ul>
<li>creation technology</li>
<li>图表</li>
</ul>
</li>
<li><p>经济管理</p>
<ul>
<li><p>网络购物</p>
<ul>
<li>XX commercial transaction</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>第二段</p>
<ul>
<li><p>原因分析</p>
<ul>
<li>由于什么现象，我要指出</li>
</ul>
</li>
<li><p>引出原因</p>
<ul>
<li>简单句+although</li>
<li>简单句+which</li>
<li>同位语从句</li>
</ul>
</li>
</ul>
</li>
<li><p>文化很重要</p>
<ul>
<li>开阔国人视野，虽然外国文化有缺陷</li>
<li>促进中国经济发展</li>
<li>如果不注重文化活动，在不远的未来会有一些问题</li>
</ul>
</li>
<li><p>段首句加工</p>
<ul>
<li><p>强调句</p>
<ul>
<li>it is …… that</li>
</ul>
</li>
<li><p>插入语</p>
<ul>
<li>+never fail to</li>
</ul>
</li>
</ul>
</li>
<li><p>呼吁</p>
<ul>
<li>行动的名言</li>
</ul>
</li>
<li><p>中国经济变好了，人们的生活质量得到提高</p>
</li>
<li><p>第一段</p>
<ul>
<li>what keeps my outlook  in the cartoon is that 图片描述</li>
<li>the symbol meaning of the cartoon is quite conspicuous ——</li>
<li>sth proves so essential/grave that it seems high time to focus on the issue</li>
</ul>
</li>
<li><p>第二段</p>
<ul>
<li>there seem at least three causes for the phenomenon</li>
</ul>
</li>
<li><p>第三段</p>
<ul>
<li>consequently，sth proves to youngsters on campus as water is to fish</li>
<li>parents,as the primary factors in children’s education,should never fail to……</li>
<li>then as a private individual,sth ???</li>
<li><p>just as  a well-noted writer has put it “”</p>
<ul>
<li>should not the issue be worthy of our attention</li>
</ul>
</li>
</ul>
</li>
<li><p>替换</p>
<ul>
<li><p>little wonder</p>
<ul>
<li>as every one can see it</li>
<li>in the general routine of everyday living</li>
</ul>
</li>
<li><p>factor</p>
<ul>
<li>reason</li>
<li>cause</li>
<li>element</li>
</ul>
</li>
<li><p>phenomenon</p>
<ul>
<li>issue</li>
<li>current situation</li>
<li>the matter</li>
<li>subject</li>
</ul>
</li>
<li><p>shed light on</p>
<ul>
<li>place great emphasis on</li>
</ul>
</li>
<li><p>many</p>
</li>
</ul>
</li>
<li><p>首先其次最后</p>
<ul>
<li>,to begin with,</li>
<li>in addition</li>
<li>consequently</li>
</ul>
</li>
<li><p>子主题 26</p>
</li>
</ul>
<h2 id="分支主题-2"><a href="#分支主题-2" class="headerlink" title="分支主题 2"></a>分支主题 2</h2>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/15/%E8%8B%B1%E8%AF%AD/%E8%8B%B1%E8%AF%AD/" data-id="cl403sxsh004af8vu7afi2r1i" data-title="英语" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-计算机组成原理/计算机组成原理" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/15/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/" class="article-date">
  <time class="dt-published" datetime="2021-12-15T13:34:55.000Z" itemprop="datePublished">2021-12-15</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/">计算机组成原理</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/15/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/">计算机组成原理</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="计算机组成原理"><a href="#计算机组成原理" class="headerlink" title="计算机组成原理"></a>计算机组成原理</h1><h2 id="绪论"><a href="#绪论" class="headerlink" title="绪论"></a>绪论</h2><h3 id="主要内容"><a href="#主要内容" class="headerlink" title="主要内容"></a>主要内容</h3><h4 id="基本部件的结构与组织方式"><a href="#基本部件的结构与组织方式" class="headerlink" title="基本部件的结构与组织方式"></a>基本部件的结构与组织方式</h4><h4 id="基本运算的操作原理"><a href="#基本运算的操作原理" class="headerlink" title="基本运算的操作原理"></a>基本运算的操作原理</h4><h4 id="基本部件和单元的设计思想"><a href="#基本部件和单元的设计思想" class="headerlink" title="基本部件和单元的设计思想"></a>基本部件和单元的设计思想</h4><h3 id="计算机系统-选择"><a href="#计算机系统-选择" class="headerlink" title="计算机系统  选择"></a>计算机系统  选择</h3><ul>
<li>硬件<ul>
<li>计算机实体<ul>
<li>主机</li>
<li>外设</li>
</ul>
</li>
</ul>
</li>
<li><p>软件</p>
<ul>
<li>具有各类特殊功能的信息组成</li>
<li><p>系统软件</p>
<ul>
<li>语言处理程序</li>
<li>操作系统</li>
<li>数据库管理系统</li>
<li>网络软件</li>
</ul>
</li>
<li><p>应用软件</p>
</li>
</ul>
</li>
</ul>
<h3 id="计算机发展历史-选择"><a href="#计算机发展历史-选择" class="headerlink" title="计算机发展历史  选择"></a>计算机发展历史  选择</h3><p><img src="C:\Users\admin\Downloads\IMG_20201205_160610.jpg" alt="IMG_20201205_160610"></p>
<ul>
<li><p>第一代计算机</p>
<ul>
<li>电子管</li>
</ul>
</li>
<li><p>第二代计算机</p>
<ul>
<li>晶体管</li>
</ul>
</li>
<li><p>第三代计算机</p>
<ul>
<li>中小规模集成电路</li>
</ul>
</li>
<li><p>第四代计算机</p>
<ul>
<li>超大规模集成电路</li>
</ul>
</li>
</ul>
<h3 id="计算机的分类"><a href="#计算机的分类" class="headerlink" title="计算机的分类"></a>计算机的分类</h3><ul>
<li><p>类别</p>
<ul>
<li>电子模拟计算机</li>
<li><p>电子数字计算机</p>
<ul>
<li><p>通用计算机</p>
<ul>
<li>巨型机</li>
<li>大型机</li>
<li>中型机</li>
<li>小型机</li>
<li>微型机</li>
<li>单片机</li>
</ul>
</li>
<li><p>专用计算机</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>指令流数据流</p>
<ul>
<li><p>单指令流单数据流</p>
<ul>
<li>冯诺依曼</li>
</ul>
</li>
<li><p>单指令流 多数据流</p>
<ul>
<li>阵列处理器</li>
<li>向量处理器</li>
</ul>
</li>
<li><p>多指令流多数据流</p>
<ul>
<li>多处理器</li>
<li>多计算机</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="计算机的发展方向"><a href="#计算机的发展方向" class="headerlink" title="计算机的发展方向"></a>计算机的发展方向</h3><ul>
<li>两极分化</li>
</ul>
<h3 id="计算机的硬件组成"><a href="#计算机的硬件组成" class="headerlink" title="计算机的硬件组成"></a>计算机的硬件组成</h3><ul>
<li><p>冯诺依曼计算机</p>
<ul>
<li>运算器、存储器、控制器、输入设备、输出设备</li>
<li>指令与数据一同等地位存于存储器内，并可按地址寻址</li>
<li>指令与数据均用二进制代码表示</li>
<li>指令由操作码地址码组成，操作码</li>
<li>指令在存储器内按顺序存放，顺序执行</li>
<li>早期的是以运算器为中心</li>
<li>运算方式</li>
<li>控制流驱动</li>
<li><p>原始数据+计算步骤</p>
<ul>
<li><p>输入设备</p>
<ul>
<li>存储器</li>
<li></li>
<li></li>
<li><p>运算器</p>
<ul>
<li><p>输出设备</p>
<ul>
<li>计算结果</li>
</ul>
</li>
</ul>
</li>
<li></li>
<li></li>
<li>控制器</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>现代计算机的组成结构</p>
<ul>
<li>运算器</li>
<li>控制器</li>
<li>主存储器</li>
<li>输入设备</li>
<li>输出设备</li>
<li>辅助存储器</li>
</ul>
</li>
<li><p>计算机的功能部件</p>
<ul>
<li><p>存储器</p>
<ul>
<li><p>MAR</p>
<ul>
<li>地址存储器</li>
</ul>
</li>
<li><p>MDR</p>
<ul>
<li>数据存储器</li>
</ul>
</li>
<li><p>地址寄存器</p>
</li>
<li>存储器</li>
<li>数据寄存器</li>
<li>n 为地址有2^n个存储单元</li>
<li>总容量=存储单元个数X存储字长</li>
</ul>
</li>
<li><p>运算器</p>
<ul>
<li><p>MQ</p>
<ul>
<li>乘方运算器</li>
</ul>
</li>
<li><p>ACC</p>
</li>
<li><p>ALU</p>
<ul>
<li>子主题 1</li>
</ul>
</li>
<li><p>X</p>
</li>
<li>PSW</li>
</ul>
</li>
<li><p>控制器</p>
<ul>
<li><p>CU</p>
<ul>
<li>控制单元</li>
</ul>
</li>
<li><p>IR</p>
<ul>
<li><p>指令寄存器</p>
<ul>
<li>子主题 1</li>
</ul>
</li>
</ul>
</li>
<li><p>PC</p>
<ul>
<li>程序计数器</li>
</ul>
</li>
</ul>
</li>
<li><p>输入设备</p>
</li>
<li>输出设备</li>
</ul>
</li>
<li><p>计算机的工作过程</p>
<ul>
<li>M</li>
<li>M()</li>
<li>()</li>
<li><p>OP()</p>
<ul>
<li>去操作码</li>
</ul>
</li>
<li><p>Ad()</p>
<ul>
<li>取地址码</li>
</ul>
</li>
<li><p>相关简称</p>
<ul>
<li><p>IR</p>
<ul>
<li>存放当前欲执行指令</li>
</ul>
</li>
<li><p>PC</p>
<ul>
<li>存放下一条指令地址</li>
</ul>
</li>
<li><p>MAR</p>
<ul>
<li>存放欲访问存储单元的地址</li>
</ul>
</li>
<li><p>MDR</p>
<ul>
<li>存放从存储单元取出的数据</li>
</ul>
</li>
</ul>
</li>
<li><p>取数指令</p>
<ul>
<li>(PC)-&gt;MAR</li>
<li>M(MAR)-&gt;MDR</li>
<li>(MDR)-&gt;IR</li>
<li>取指令结束</li>
<li>OP(IR)-&gt;CU</li>
<li>分析指令结束</li>
<li>AD(IR)-&gt;MAR</li>
<li>M(MAR)-&gt;MDR</li>
<li>(MDR)-&gt;ACC</li>
<li>执行指令结束</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="计算机系统的多层次结构"><a href="#计算机系统的多层次结构" class="headerlink" title="计算机系统的多层次结构"></a>计算机系统的多层次结构</h3><ul>
<li>高级语言机器</li>
<li><p>虚拟机器</p>
<ul>
<li>汇编语言层</li>
<li>操作系统机器</li>
</ul>
</li>
<li><p>用机器语言的机器</p>
</li>
<li>微指令系统</li>
</ul>
<h3 id="计算机的性能指标"><a href="#计算机的性能指标" class="headerlink" title="计算机的性能指标"></a>计算机的性能指标</h3><ul>
<li><p>容量</p>
<ul>
<li>总容量=存储单元个数X存储字长bit</li>
<li>2^n*MDR的位数</li>
</ul>
</li>
<li><p>速度</p>
<ul>
<li><p>CPU的时钟周期</p>
<ul>
<li>CLK</li>
<li>CPU时钟频率(主频)=1/x</li>
<li>程序耗时=指令耗时=指令CPIXCPU时钟周期=平均CPIX指令条数XCPU时钟周期</li>
</ul>
</li>
<li><p>CPI</p>
</li>
<li><p>MIPS</p>
<ul>
<li>指令条数/（执行条数X10^6）=主频/CPI</li>
</ul>
</li>
<li><p>MFLOPS</p>
</li>
<li>CFLOPS</li>
<li>TFLOPS</li>
<li><p>数据通路带宽</p>
<ul>
<li>数据总线一次并行传输的位数</li>
</ul>
</li>
<li><p>吞吐量</p>
<ul>
<li>单位时间处理请求的数量</li>
</ul>
</li>
<li><p>响应时间</p>
<ul>
<li>系统对请求做出响应并获得他所需要的结果的等待时间</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="第二章数据的表示与运算"><a href="#第二章数据的表示与运算" class="headerlink" title="第二章数据的表示与运算"></a>第二章数据的表示与运算</h2><h3 id="计算机-数的表示"><a href="#计算机-数的表示" class="headerlink" title="计算机 数的表示"></a>计算机 数的表示</h3><ul>
<li>机器数</li>
<li>真值</li>
<li><p>定点表示</p>
<ul>
<li><p>小数</p>
<ul>
<li><p>最大正数</p>
<ul>
<li>0.1111111</li>
</ul>
</li>
<li><p>最小正数</p>
<ul>
<li>0.000001</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>浮点表示</p>
<ul>
<li>N=Mxr^E</li>
<li>r=2</li>
<li><p>最大正数</p>
<ul>
<li><p>(1-2^(-n))x2^(2^k-1)</p>
<ul>
<li>阶码于尾数均为最大正数</li>
</ul>
</li>
</ul>
</li>
<li><p>最小正数</p>
<ul>
<li><p>2^-nx2^(-2^k)</p>
<ul>
<li>尾数最小正数，阶码绝对值最大负数</li>
</ul>
</li>
</ul>
</li>
<li><p>绝对值最大负数</p>
<ul>
<li>-1x2^(2^k-1)</li>
</ul>
</li>
</ul>
</li>
<li><p>表示范围</p>
</li>
<li><p>规格化浮点数</p>
<ul>
<li>规定尾数的最高数位必须是一个有效值</li>
<li><p>尾数为正</p>
<ul>
<li>形式：0.1XXXXXXXXXXXXX</li>
</ul>
</li>
<li><p>尾数为负</p>
<ul>
<li>形式：1.0XXXXXXX</li>
</ul>
</li>
<li><p>左规</p>
<ul>
<li><p>尾数算数左移n位</p>
<ul>
<li>阶码-n</li>
</ul>
</li>
</ul>
</li>
<li><p>右规</p>
<ul>
<li>当浮点数运算出现溢出，将尾数右移，阶码+1</li>
</ul>
</li>
</ul>
</li>
<li><p>IEEE754标准</p>
<ul>
<li>数符+阶码(移码)+尾数(原码)</li>
<li><p>短浮点数</p>
<ul>
<li><p>float</p>
<ul>
<li><p>1+8+23=32     127</p>
<ul>
<li>N=(-1)^s<em>1.M</em>2^(E-127)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>长浮点数</p>
<ul>
<li><p>double</p>
<ul>
<li><p>1+11+52=64     1023</p>
<ul>
<li>N=(-1)^s<em>1.M</em>2^(E-1023)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>临时浮点数</p>
</li>
</ul>
</li>
<li><p>浮点数加减</p>
<ul>
<li><p>对阶</p>
<ul>
<li>小阶对大阶</li>
</ul>
</li>
<li><p>尾数求和</p>
</li>
<li>规格化</li>
<li>舍入</li>
<li>与补码的移位相同</li>
<li><p>溢出判断</p>
<ul>
<li><p>01</p>
<ul>
<li><p>上溢</p>
<ul>
<li>中断处理</li>
</ul>
</li>
</ul>
</li>
<li><p>10</p>
<ul>
<li><p>下溢</p>
<ul>
<li>机器零处理</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="计算机的运算方法"><a href="#计算机的运算方法" class="headerlink" title="计算机的运算方法"></a>计算机的运算方法</h3><h3 id="运算器的设计"><a href="#运算器的设计" class="headerlink" title="运算器的设计"></a>运算器的设计</h3><h3 id="数的编码"><a href="#数的编码" class="headerlink" title="数的编码"></a>数的编码</h3><ul>
<li><p>进位计数法</p>
<ul>
<li><p>一进制数</p>
<ul>
<li>1111111111111111111111111</li>
</ul>
</li>
<li><p>二进制</p>
<ul>
<li>1010101</li>
</ul>
</li>
<li><p>十进制</p>
<ul>
<li>1234567890</li>
</ul>
</li>
<li><p>十六进制</p>
<ul>
<li>0123456789ABCDEF</li>
</ul>
</li>
</ul>
</li>
<li><p>进制转换</p>
<ul>
<li><p>十进制与其他进制</p>
<ul>
<li>kn*r^n+……+k1r^1</li>
</ul>
</li>
<li><p>二进制与二的指数进制</p>
</li>
</ul>
</li>
<li><p>BCD码</p>
</li>
<li><p>余3码</p>
<ul>
<li>+0011</li>
</ul>
</li>
<li><p>ASCII码</p>
<ul>
<li>7位二进制</li>
<li>0-31</li>
<li>控制编码</li>
<li>32-</li>
<li>空格</li>
<li>32-126</li>
<li>可印刷字符</li>
<li>子主题 8</li>
</ul>
</li>
<li><p>汉字</p>
<ul>
<li>输入码</li>
<li>汉字字形码</li>
<li><p>GB2312-80</p>
<ul>
<li>区位码</li>
<li><p>国标码</p>
<ul>
<li>+20H</li>
</ul>
</li>
<li><p>汉字内码</p>
<ul>
<li>+80H</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>校验码</p>
<ul>
<li><p>码距</p>
<ul>
<li>两个合法码字对应位上数字的不同位的个数</li>
</ul>
</li>
<li><p>奇偶校验码</p>
<ul>
<li><p>奇校验</p>
<ul>
<li>有奇数个1</li>
</ul>
</li>
<li><p>偶校验</p>
</li>
</ul>
</li>
<li><p>海明校验码</p>
<ul>
<li>多重奇偶校验码</li>
<li>发现错误位，进行纠错</li>
</ul>
</li>
<li><p>分组校验</p>
</li>
<li><p>n 信息位  k 校验位</p>
<ul>
<li>n+k个位置</li>
<li>1个正确的状态</li>
<li>z^k状态</li>
</ul>
</li>
<li><p>循环冗余校验码</p>
<ul>
<li><p>发送端</p>
<ul>
<li>将k位二进制信息左移k位，将他与生成多项式G(x)做模2除法，生成R位校验码</li>
<li>k+R拼接成码字</li>
</ul>
</li>
<li><p>接收端</p>
<ul>
<li>做模2除法，余数为零，正确，否则，丢弃\纠错</li>
</ul>
</li>
</ul>
</li>
<li><p>BCD码</p>
<ul>
<li>4位2进制表示一位十进制0-9这10个数码</li>
<li>8421码</li>
<li><p>余3码</p>
<ul>
<li>+(0011)2</li>
</ul>
</li>
<li><p>2421码</p>
<ul>
<li>权值2、4、2、1</li>
<li>大于等于5的4位二进制的最高位位1，否则，0</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="加法器"><a href="#加法器" class="headerlink" title="加法器"></a>加法器</h3><ul>
<li><p>一位全加器</p>
<ul>
<li><p>输入</p>
<ul>
<li>加数Ai</li>
<li>加数Bi</li>
<li>低位进位Ci-1</li>
</ul>
</li>
<li><p>输出</p>
<ul>
<li>和Si</li>
<li>进位Ci</li>
</ul>
</li>
<li><p>Si=Ai⊕Bi⊕Ci-1</p>
</li>
<li>Ci=AiBi+(Ai⊕Bi)Ci-1</li>
</ul>
</li>
<li><p>串行加法器</p>
<ul>
<li>一个全加器，数据逐行串行送入</li>
<li>成本低，速度慢</li>
</ul>
</li>
<li><p>并行加法器</p>
<ul>
<li>位数与机器字长相同，数据同时运算</li>
<li>需要考虑低位相加会影响高位运算结果</li>
<li>串行进位</li>
<li><p>并行进位</p>
<ul>
<li><p>单极先行进位方式</p>
<ul>
<li>组内并行、组间串行</li>
</ul>
</li>
<li><p>多级先行进位方式</p>
<ul>
<li>组内并行、组间并行</li>
</ul>
</li>
</ul>
</li>
<li><p>各级低位产生的信号依次同时送到高位各全加器，同时形成进位信号</p>
</li>
</ul>
</li>
</ul>
<h2 id="第三章-存储系统"><a href="#第三章-存储系统" class="headerlink" title="第三章 存储系统"></a>第三章 存储系统</h2><h3 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h3><ul>
<li><p>分类</p>
<ul>
<li><p>在计算机中的作用</p>
<ul>
<li>主存</li>
<li>辅存</li>
<li>高速缓冲存储器(cache)</li>
</ul>
</li>
<li><p>存取方式</p>
<ul>
<li><p>随机存取存储器</p>
<ul>
<li>RAM</li>
</ul>
</li>
<li><p>只读存储器</p>
<ul>
<li>ROM</li>
</ul>
</li>
<li><p>顺序存取存储器</p>
<ul>
<li>SAM</li>
</ul>
</li>
<li><p>直接存取存储器</p>
<ul>
<li>DAM</li>
</ul>
</li>
</ul>
</li>
<li><p>存储介质</p>
<ul>
<li>磁芯存储器</li>
<li><p>半导体存储器</p>
<ul>
<li><p>随机存取(存取时间与存储单元无关)</p>
<ul>
<li>ROM</li>
<li>RAM</li>
</ul>
</li>
<li><p>易失</p>
</li>
</ul>
</li>
<li><p>磁表面存储器</p>
<ul>
<li>顺序存取</li>
<li>非易失的</li>
<li>破坏性读取</li>
</ul>
</li>
<li><p>光存储器</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>性能指标</p>
<ul>
<li><p>基本指标</p>
<ul>
<li><p>存储容量</p>
<ul>
<li>存储字数X字长</li>
</ul>
</li>
<li><p>单位成本</p>
<ul>
<li>每位价格=总成本/总容量</li>
</ul>
</li>
<li><p>存储速度</p>
<ul>
<li>数据传输率=数据的宽度/存储周期</li>
</ul>
</li>
</ul>
</li>
<li><p>存取时间</p>
<ul>
<li>从启动一次存储器操作到完成该操作所经历的时间</li>
<li>读入时间</li>
<li>写入时间</li>
</ul>
</li>
<li><p>主存带宽</p>
<ul>
<li>每秒从主存进出信息的最大数量，字/秒  位/秒</li>
<li>数据传输率</li>
</ul>
</li>
<li><p>存取周期</p>
<ul>
<li>恢复时间</li>
</ul>
</li>
</ul>
</li>
<li><p>层次化结构</p>
<ul>
<li>cache主存层</li>
<li><p>存储器的层次结构</p>
<ul>
<li>CPU</li>
<li></li>
<li></li>
<li><p>主存</p>
<ul>
<li>辅存</li>
</ul>
</li>
<li></li>
<li>cache</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="半导体存储器"><a href="#半导体存储器" class="headerlink" title="半导体存储器"></a>半导体存储器</h3><ul>
<li><p>SRAM DRAM</p>
<ul>
<li>SRAM</li>
<li><p>特点</p>
<ul>
<li>存储信息</li>
<li><p>触发器(双稳态)</p>
<ul>
<li>非破坏性</li>
<li><p>破坏性</p>
<ul>
<li>不需要刷新</li>
<li><p>刷新</p>
<ul>
<li>同时送</li>
<li><p>送行列地址</p>
<ul>
<li>快</li>
<li><p>运行速度</p>
<ul>
<li>低</li>
<li><p>集成度</p>
<ul>
<li>高</li>
<li><p>发热</p>
<ul>
<li>高</li>
<li>存储成本</li>
<li>底</li>
</ul>
</li>
<li><p>小</p>
</li>
</ul>
</li>
<li><p>高</p>
</li>
</ul>
</li>
<li><p>慢</p>
</li>
</ul>
</li>
<li><p>分两次送</p>
</li>
</ul>
</li>
<li><p>需要刷新</p>
</li>
</ul>
</li>
<li><p>破坏性读出</p>
</li>
</ul>
</li>
<li><p>电容</p>
</li>
</ul>
</li>
<li><p>DRAM</p>
</li>
</ul>
</li>
<li><p>存储芯片的基本结构</p>
<ul>
<li><p>地址线</p>
<ul>
<li><p>10</p>
<ul>
<li><p>14</p>
<ul>
<li>13</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>译码驱动</p>
<ul>
<li>将来自地址总线的地址信号翻译成对应存储单元的联通信号</li>
</ul>
</li>
<li><p>片选线</p>
<ul>
<li>cs ce</li>
</ul>
</li>
<li><p>存储矩阵</p>
<ul>
<li>大量相同单位存储单元阵列构成</li>
</ul>
</li>
<li><p>读写电路</p>
<ul>
<li>we(低电平写 高电平读)</li>
<li>oe we</li>
</ul>
</li>
<li><p>数据线</p>
<ul>
<li><p>4</p>
<ul>
<li><p>1</p>
<ul>
<li>8</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>芯片容量</p>
<ul>
<li><p>1kx4位</p>
<ul>
<li><p>16kx1</p>
<ul>
<li>8kx8</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>ROM的特点</p>
</li>
<li><p>DRAM的 刷新</p>
<ul>
<li>刷新周期：2ms</li>
<li>一行为单位，每次刷新一行存储单元</li>
<li>行列地址，减收选通线数量</li>
<li><p>刷新时刻：</p>
<ul>
<li>分散刷新</li>
<li><p>集中刷新</p>
<ul>
<li>死区</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="主存-cache地址映射"><a href="#主存-cache地址映射" class="headerlink" title="主存-cache地址映射"></a>主存-cache地址映射</h3><ul>
<li><p>直接映射</p>
<ul>
<li>主存只能装入cache中的唯一位置，如果这有内容，则替换</li>
<li>主存子块标志+cache字块地址+子块内地址</li>
</ul>
</li>
<li><p>全相联映射</p>
<ul>
<li>主存数据快装入cache中任何位置，cache冲突率低</li>
<li>主存字块标记+子块内地址</li>
</ul>
</li>
<li><p>组相联映射</p>
<ul>
<li>将cache空间分成大小相同的组，主存的数据块可以装入到一组内的任何位置，组剑直接映射，组内全相连</li>
<li>主存字块标志+附加tag+组号+子块内地址</li>
</ul>
</li>
</ul>
<h3 id="cache-主存替换算法"><a href="#cache-主存替换算法" class="headerlink" title="cache-主存替换算法"></a>cache-主存替换算法</h3><ul>
<li>随机算法</li>
<li>随机地确定替换的cache块。</li>
<li>先进先出算法</li>
<li>选择最早调入的行替换</li>
<li>近期最少使用算法</li>
<li>依据程序访问的局部性原理选择近期内长期未访问的存储行作为被替换的行</li>
<li>cache写策略</li>
</ul>
<h3 id="存储器与CPU的协同"><a href="#存储器与CPU的协同" class="headerlink" title="存储器与CPU的协同"></a>存储器与CPU的协同</h3><ul>
<li>存储器的简单模型及寻址</li>
<li>主存与CPU的链接</li>
<li><p>双口RAM与多模块存储器</p>
<ul>
<li>存取周期</li>
<li><p>双端口RAM</p>
<ul>
<li>空间</li>
</ul>
</li>
<li><p>多模块存储器</p>
<ul>
<li>时间</li>
</ul>
</li>
</ul>
</li>
<li><p>高速缓冲存储器</p>
<ul>
<li>程序访问的局部原理</li>
<li>时间局部性原理</li>
<li>空间局部性原理</li>
<li>cache性能衡量的指标</li>
<li>命中率</li>
<li>程序执行期间，cache总命中次数N1，访问主存N2</li>
<li>H=N1/（N1+N2）</li>
<li>效率</li>
<li>e=访问cache的时间/平均访问时间</li>
<li>e=t1/((h<em>t1)+(1-h</em>t2))</li>
</ul>
</li>
<li><p>虚拟存储器</p>
</li>
</ul>
<h3 id="子主题-4"><a href="#子主题-4" class="headerlink" title="子主题 4"></a>子主题 4</h3><h2 id="第四章-指令系统"><a href="#第四章-指令系统" class="headerlink" title="第四章 指令系统"></a>第四章 指令系统</h2><h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><ul>
<li><p>指令</p>
<ul>
<li>是指计算机执行某相运算或处理功能的命令</li>
</ul>
</li>
<li><p>指令系统</p>
<ul>
<li>计算机使用的全部指令组成该计算机的指令系统</li>
<li>指令系统是计算机的主要属性，位于硬件与软件交界面</li>
</ul>
</li>
</ul>
<h3 id="指令类型"><a href="#指令类型" class="headerlink" title="指令类型"></a>指令类型</h3><ul>
<li><p>数据传送指令</p>
<ul>
<li><p>一般传送指令</p>
<ul>
<li>数据从源地址到目的地址，源地址的内存保持不变</li>
<li>MOV</li>
<li><p>分类</p>
<ul>
<li>主存单元之间的传递</li>
<li>主存单元-》寄存器</li>
<li>寄存器-》主存单元</li>
<li>寄存器间的传递</li>
</ul>
</li>
</ul>
</li>
<li><p>堆栈操作指令</p>
<ul>
<li>进栈、出栈</li>
</ul>
</li>
<li><p>数据交换指令</p>
<ul>
<li>将原操作数与目的操作数(一个字节或一个字)相互交换位置</li>
</ul>
</li>
</ul>
</li>
<li><p>运算类指令</p>
<ul>
<li><p>算术运算类指令</p>
<ul>
<li>定点数、浮点数的运算</li>
</ul>
</li>
<li><p>逻辑运算类指令</p>
</li>
<li>移位类指令</li>
</ul>
</li>
<li><p>程序控制类指令</p>
<ul>
<li><p>转移指令</p>
<ul>
<li><p>改变程序执行顺序</p>
<ul>
<li>JMP</li>
</ul>
</li>
</ul>
</li>
<li><p>子程序调用指令</p>
<ul>
<li><p>主程序转向子程序的指令</p>
<ul>
<li>CALL</li>
</ul>
</li>
</ul>
</li>
<li><p>返回指令</p>
<ul>
<li>RET</li>
</ul>
</li>
</ul>
</li>
<li><p>输入输出指令</p>
<ul>
<li>CISC</li>
<li><p>树干</p>
<ul>
<li>复杂、庞大</li>
<li><p>指令系统</p>
<ul>
<li><blockquote>
<p>200</p>
</blockquote>
</li>
<li><p>指令数目</p>
<ul>
<li>不固定</li>
<li><p>指令字长</p>
<ul>
<li>不限制</li>
<li><p>可访存空间</p>
<ul>
<li>相差较大</li>
<li><p>指令执行时间</p>
<ul>
<li>相差较大</li>
<li><p>指令使用频率</p>
<ul>
<li><p>通用寄存器</p>
<ul>
<li><p>控制方式</p>
<ul>
<li><p>指令流水</p>
<ul>
<li><p>目标代码</p>
<ul>
<li>寻址方式</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>dou’j</p>
</li>
</ul>
</li>
<li><p>大多数一个周期</p>
</li>
</ul>
</li>
<li><p>重用load/store指令</p>
</li>
</ul>
</li>
<li><p>定长</p>
</li>
</ul>
</li>
<li><p>&lt;100</p>
</li>
</ul>
</li>
<li><p>简单、精简</p>
</li>
</ul>
</li>
<li><p>RISC</p>
</li>
</ul>
</li>
</ul>
<h3 id="指令格式"><a href="#指令格式" class="headerlink" title="指令格式"></a>指令格式</h3><ul>
<li><p>指令基本格式</p>
<ul>
<li><p>机器指令</p>
<ul>
<li>由cpu可以直接执行的指令</li>
</ul>
</li>
<li><p>操作码+地址码</p>
<ul>
<li><p>零地址码</p>
<ul>
<li>空操作、停机操作、关中段</li>
</ul>
</li>
<li><p>一地址指令</p>
<ul>
<li>只有目的操作数的单操作数指令</li>
<li>按A1地址读取操作数，结果存回源地址0000000000000000000000000000</li>
<li>隐含约定目的地址的双操作数指令(ACC提供)</li>
</ul>
</li>
<li><p>二地址指令</p>
<ul>
<li>（A1）OP（A2）-&gt;A1</li>
</ul>
</li>
<li><p>三地址指令</p>
<ul>
<li>（A1）OP（A2）-&gt;A3</li>
</ul>
</li>
<li><p>四地址指令</p>
<ul>
<li>（A1）OP（A2）-&gt;A3   A4=下一条将要执行的指令的地址</li>
</ul>
</li>
</ul>
</li>
<li><p>操作数</p>
<ul>
<li><p>存放方式</p>
<ul>
<li>大端方式</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>地址码的个数</p>
</li>
<li><p>定长操作码和变长操作吗</p>
<ul>
<li>长度固定</li>
<li><p>长度可变</p>
<ul>
<li>OP A1 A2 A3 A4</li>
<li>(A1)OP(A2)-&gt;A3  A4=下一条执行指令的地址</li>
</ul>
</li>
</ul>
</li>
<li><p>指令周期</p>
<ul>
<li><p>CPU从主存取出并指像一条指令的所需的全部时间</p>
<ul>
<li>取值周期</li>
<li>间质周期</li>
<li>执行周期</li>
<li>中断周期</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="编址方式"><a href="#编址方式" class="headerlink" title="编址方式"></a>编址方式</h3><ul>
<li><p>编址</p>
<ul>
<li>通用寄存器</li>
<li>主存储器</li>
<li>输入输出设备</li>
<li><p>I/O接口</p>
<ul>
<li>统一编址方法</li>
<li>独立编址方法</li>
</ul>
</li>
</ul>
</li>
<li><p>编址单位</p>
</li>
<li>字编址</li>
<li>每个编制单位所包含的信息量与读或写一次寄存器，主存获得的信息量是相同的</li>
<li>字节编址方法</li>
<li>是编址单位与信息的基本单位一致</li>
<li>位编址</li>
</ul>
<h3 id="寻址方式"><a href="#寻址方式" class="headerlink" title="寻址方式"></a>寻址方式</h3><ul>
<li>确定本条指令的操作数地址，吓一跳指令的指令地址</li>
<li><p>指令寻址方式</p>
<ul>
<li><p>始终由PC给出</p>
<ul>
<li><p>顺序寻址</p>
<ul>
<li>(PC)+1-&gt;PC</li>
</ul>
</li>
<li><p>跳跃寻址</p>
<ul>
<li>由转移指令给出</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>数据寻址</p>
<ul>
<li><p>操作码+寻址特征+形式地址</p>
<ul>
<li>有效地址</li>
</ul>
</li>
<li><p>指令子长=存储字长=机器字长</p>
</li>
<li><p>隐含寻址</p>
<ul>
<li><p>不是给出操作数地址，而是在指令中隐含着操作数地址</p>
<ul>
<li><p>缩短指令子长</p>
<ul>
<li>增加存储操作数或隐含地址的硬件</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>立即寻址</p>
<ul>
<li></li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="第五章-输入输出系统"><a href="#第五章-输入输出系统" class="headerlink" title="第五章 输入输出系统"></a>第五章 输入输出系统</h2><h3 id="IO接口"><a href="#IO接口" class="headerlink" title="IO接口"></a>IO接口</h3><ul>
<li>输入输出接口是主机与外设的交接界面</li>
</ul>
<h3 id="IO接口的功能"><a href="#IO接口的功能" class="headerlink" title="IO接口的功能"></a>IO接口的功能</h3><ul>
<li>实现主机与外设的通信联络控制</li>
<li>进行地址移码与设备选择</li>
<li>实现数据缓冲</li>
<li>信号格式的转换</li>
<li>传送控制命令和状态信息</li>
</ul>
<h3 id="IO端口"><a href="#IO端口" class="headerlink" title="IO端口"></a>IO端口</h3><ul>
<li>可以被CPU直接访问的寄存器</li>
</ul>
<h3 id="IO端口编址"><a href="#IO端口编址" class="headerlink" title="IO端口编址"></a>IO端口编址</h3><ul>
<li><p>统一编址</p>
<ul>
<li>当作存储器的单元进行地址分配，不需要设置IO指令，统一的访存</li>
</ul>
</li>
<li><p>独立编址</p>
<ul>
<li>IO端口与存储器地址无关，独立编址的cPU需要设置专门的输入和输出操作</li>
</ul>
</li>
</ul>
<h3 id="IO方式"><a href="#IO方式" class="headerlink" title="IO方式"></a>IO方式</h3><h3 id="程序查询方式"><a href="#程序查询方式" class="headerlink" title="程序查询方式"></a>程序查询方式</h3><ul>
<li><p>信息交换由主机执行程序实现</p>
<ul>
<li>数据缓冲寄存器</li>
<li>状态寄存器</li>
</ul>
</li>
<li><p>开始</p>
<ul>
<li><p>预制传送参数</p>
<ul>
<li><p>启动外设</p>
<ul>
<li><p>读取外设状态</p>
<ul>
<li><p>外设就绪</p>
<ul>
<li><p>传送一次</p>
<ul>
<li><p>修改传送参数</p>
<ul>
<li><p>传送完成</p>
<ul>
<li>结束</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="程序中断方式"><a href="#程序中断方式" class="headerlink" title="程序中断方式"></a>程序中断方式</h3><ul>
<li><p>中断源</p>
<ul>
<li>自愿中断、强迫中断</li>
<li><p>程序中断</p>
<ul>
<li>简单中断</li>
</ul>
</li>
<li><p>内中断</p>
<ul>
<li>外中断</li>
</ul>
</li>
<li><p>单重中断</p>
<ul>
<li>多重中断</li>
</ul>
</li>
</ul>
</li>
<li><p>中断请求信号</p>
<ul>
<li><p>独立请求线</p>
<ul>
<li>硬件量大</li>
</ul>
</li>
<li><p>公共请求线</p>
<ul>
<li>易扩展</li>
</ul>
</li>
<li><p>二维结构</p>
<ul>
<li>同一优先级的共用一根请求线</li>
</ul>
</li>
</ul>
</li>
<li><p>优先级</p>
<ul>
<li><p>故障</p>
<ul>
<li><p>简单中断</p>
<ul>
<li><p>IO设置中断</p>
<ul>
<li><p>软件中断</p>
<ul>
<li><p>非屏蔽中断</p>
<ul>
<li>可屏蔽中断</li>
</ul>
</li>
<li><p>DMA请求</p>
<ul>
<li>普通IO设备传送中断请求</li>
</ul>
</li>
<li><p>高速</p>
</li>
<li>低速</li>
<li>输入设备</li>
<li>输出设备</li>
<li>实时设备</li>
<li>普通设备</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="DMA方式"><a href="#DMA方式" class="headerlink" title="DMA方式"></a>DMA方式</h3><h3 id="通道方式"><a href="#通道方式" class="headerlink" title="通道方式"></a>通道方式</h3><h3 id="子主题-15"><a href="#子主题-15" class="headerlink" title="子主题 15"></a>子主题 15</h3><h3 id="子主题-6"><a href="#子主题-6" class="headerlink" title="子主题 6"></a>子主题 6</h3><h3 id="子主题-4-1"><a href="#子主题-4-1" class="headerlink" title="子主题 4"></a>子主题 4</h3><h2 id="第七章-输入输出系统"><a href="#第七章-输入输出系统" class="headerlink" title="第七章  输入输出系统"></a>第七章  输入输出系统</h2><h3 id="IO系统的基本概念"><a href="#IO系统的基本概念" class="headerlink" title="IO系统的基本概念"></a>IO系统的基本概念</h3><ul>
<li>程序查询方式</li>
<li>程序中断方式</li>
<li>DMA方式</li>
<li>通道方式</li>
<li><p>输入设备</p>
<ul>
<li>键盘</li>
<li>鼠标</li>
</ul>
</li>
<li><p>输出设备</p>
<ul>
<li><p>显示器</p>
<ul>
<li>VRAM容量=分辨率X灰度级位数</li>
</ul>
</li>
<li><p>打印机</p>
</li>
</ul>
</li>
<li><p>外存储器</p>
</li>
<li><p>外部设备</p>
<ul>
<li>包括输入出即通过输入输出接口才能访问的外存储设备</li>
</ul>
</li>
<li><p>接口</p>
</li>
<li><p>io的构成</p>
<ul>
<li><p>硬件</p>
<ul>
<li>外部设备、设备控制器</li>
</ul>
</li>
<li><p>软件</p>
<ul>
<li>驱动程序、用户程序、管理程序</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="IO接口的功能-1"><a href="#IO接口的功能-1" class="headerlink" title="IO接口的功能"></a>IO接口的功能</h3><h3 id="io接口的基本结构"><a href="#io接口的基本结构" class="headerlink" title="io接口的基本结构"></a>io接口的基本结构</h3><h3 id="I-O方式"><a href="#I-O方式" class="headerlink" title="I/O方式"></a>I/O方式</h3><h2 id="00001"><a href="#00001" class="headerlink" title="00001"></a>00001</h2><h3 id="形式地址是操作数本身，用补码形式"><a href="#形式地址是操作数本身，用补码形式" class="headerlink" title="形式地址是操作数本身，用补码形式"></a>形式地址是操作数本身，用补码形式</h3><ul>
<li><p>指令执行阶段不访问主存，指令执行时间最短</p>
<ul>
<li>A的位数限制了立即数的范围</li>
</ul>
</li>
</ul>
<h3 id="直接寻址"><a href="#直接寻址" class="headerlink" title="直接寻址"></a>直接寻址</h3><ul>
<li><p>指令中的数就是操作数的真正地址EA</p>
<ul>
<li><p>简单，指令执行阶段及访问一次主存</p>
<ul>
<li>A的位数决定了该指令操作数的寻址范围，操作数地址不宜修改</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="间接寻址"><a href="#间接寻址" class="headerlink" title="间接寻址"></a>间接寻址</h3><ul>
<li><p>指令给出的操作数的地址的地址  EA=(A)</p>
<ul>
<li><p>扩大了寻址范围</p>
<ul>
<li><p>便于编写程序</p>
<ul>
<li>指令在执行阶段多次访存</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="寄存器寻址"><a href="#寄存器寻址" class="headerlink" title="寄存器寻址"></a>寄存器寻址</h3><ul>
<li><p>在指令字中直接给出操作数的寄存器编号  EA=R</p>
<ul>
<li><p>指令在执行阶段不访问主存，指令字短且执行速度快，支持向量/矩阵运算</p>
<ul>
<li>寄存器价格昂贵，寄存器有限</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="寄存器间接寻址"><a href="#寄存器间接寻址" class="headerlink" title="寄存器间接寻址"></a>寄存器间接寻址</h3><ul>
<li>寄存器给出的不是操作数，是操作数所在主存单元的地址</li>
</ul>
<h3 id="相对寻址"><a href="#相对寻址" class="headerlink" title="相对寻址"></a>相对寻址</h3><h3 id="基址寻址"><a href="#基址寻址" class="headerlink" title="基址寻址"></a>基址寻址</h3><h3 id="变址寻址"><a href="#变址寻址" class="headerlink" title="变址寻址"></a>变址寻址</h3><h3 id="堆栈寻址"><a href="#堆栈寻址" class="headerlink" title="堆栈寻址"></a>堆栈寻址</h3><h3 id="码"><a href="#码" class="headerlink" title="码"></a>码</h3><h3 id="补码乘法运算"><a href="#补码乘法运算" class="headerlink" title="补码乘法运算"></a>补码乘法运算</h3><h3 id="补码除法运算"><a href="#补码除法运算" class="headerlink" title="补码除法运算"></a>补码除法运算</h3><h3 id="浮点数"><a href="#浮点数" class="headerlink" title="浮点数"></a>浮点数</h3><h3 id="分支主题-19"><a href="#分支主题-19" class="headerlink" title="分支主题 19"></a>分支主题 19</h3><ul>
<li>Could not install packages due to an EnvironmentError: [Errno 2] No such file or directory: ‘C:\Users\admin\AppData\Local\Temp\pip-req-tracker-udjol7q6\3f43d1f8a204984328503ed4b847eedec40b9e340cb3554553324ff6’</li>
</ul>
<h3 id="小题"><a href="#小题" class="headerlink" title="小题"></a>小题</h3><ul>
<li><p>浮点数的表示</p>
<ul>
<li>普通表示</li>
<li>规格化浮点数</li>
<li>IEEE754标准浮点数</li>
</ul>
</li>
<li><p>数据效验码</p>
<ul>
<li>奇偶校验码</li>
<li>海明码</li>
<li>CRC循环冗余校验码</li>
</ul>
</li>
<li><p>数据寻址</p>
<ul>
<li>立即寻址</li>
<li>直接寻址</li>
<li>间接寻址</li>
<li>寄存器寻址</li>
<li>基址寻址‘</li>
<li>变址寻址</li>
<li>相对寻址</li>
</ul>
</li>
<li><p>计算机性能指标的计算</p>
</li>
</ul>
<h3 id="大题"><a href="#大题" class="headerlink" title="大题"></a>大题</h3><ul>
<li><p>cache的映射</p>
<ul>
<li>全相联映射</li>
<li>直接映射</li>
<li>组相联映射</li>
</ul>
</li>
<li><p>存储系统的设计</p>
</li>
<li>指令系统的设计</li>
<li><p>输入输出系统</p>
<ul>
<li>程序查询方式</li>
<li>中断方式</li>
<li>DMA方式</li>
</ul>
</li>
</ul>
<h2 id="CPU"><a href="#CPU" class="headerlink" title="CPU"></a>CPU</h2><h3 id="CPU由运算器、控制器组成"><a href="#CPU由运算器、控制器组成" class="headerlink" title="CPU由运算器、控制器组成"></a>CPU由运算器、控制器组成</h3><h3 id="运算器"><a href="#运算器" class="headerlink" title="运算器"></a>运算器</h3><ul>
<li>ALU</li>
<li>暂存器 T</li>
<li>累加器 ACC</li>
<li>通用寄存器组</li>
<li>程序状态字 PSW</li>
<li>移位器</li>
</ul>
<h3 id="控制器"><a href="#控制器" class="headerlink" title="控制器"></a>控制器</h3><ul>
<li>程序计数器</li>
<li>指令寄存器</li>
<li>指令译码器</li>
<li>存储器地址寄存器</li>
<li>存储器数据寄存器</li>
<li>时序控制功能</li>
<li>操作控制</li>
</ul>
<h3 id="控制器硬件实现方法"><a href="#控制器硬件实现方法" class="headerlink" title="控制器硬件实现方法"></a>控制器硬件实现方法</h3><h3 id="组合逻辑"><a href="#组合逻辑" class="headerlink" title="组合逻辑"></a>组合逻辑</h3><h3 id="存储逻辑"><a href="#存储逻辑" class="headerlink" title="存储逻辑"></a>存储逻辑</h3><h3 id="控制单元由们电路组成的复杂树形网络"><a href="#控制单元由们电路组成的复杂树形网络" class="headerlink" title="控制单元由们电路组成的复杂树形网络"></a>控制单元由们电路组成的复杂树形网络</h3><h3 id="一条指令-》一个微程序"><a href="#一条指令-》一个微程序" class="headerlink" title="一条指令=》一个微程序"></a>一条指令=》一个微程序</h3><h3 id="一个微程序包含多条微指令"><a href="#一个微程序包含多条微指令" class="headerlink" title="一个微程序包含多条微指令"></a>一个微程序包含多条微指令</h3><h3 id="一条微指令包含多条微操作"><a href="#一条微指令包含多条微操作" class="headerlink" title="一条微指令包含多条微操作"></a>一条微指令包含多条微操作</h3><h3 id="微指令"><a href="#微指令" class="headerlink" title="微指令"></a>微指令</h3><h3 id="操作控制字段"><a href="#操作控制字段" class="headerlink" title="操作控制字段"></a>操作控制字段</h3><h3 id="顺序控制字段"><a href="#顺序控制字段" class="headerlink" title="顺序控制字段"></a>顺序控制字段</h3><h3 id="子主题-14"><a href="#子主题-14" class="headerlink" title="子主题 14"></a>子主题 14</h3>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/15/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/" data-id="cl403sxsl004nf8vuh42j5uml" data-title="计算机组成原理" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-创造模式/创建型模式/抽象工厂模式" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/15/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/%E5%88%9B%E5%BB%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/%E6%8A%BD%E8%B1%A1%E5%B7%A5%E5%8E%82%E6%A8%A1%E5%BC%8F/" class="article-date">
  <time class="dt-published" datetime="2021-12-15T13:34:55.000Z" itemprop="datePublished">2021-12-15</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/">创造模式</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/15/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/%E5%88%9B%E5%BB%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/%E6%8A%BD%E8%B1%A1%E5%B7%A5%E5%8E%82%E6%A8%A1%E5%BC%8F/">抽象工厂模式</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、创建型模式（抽象工厂模式（Abstract-Factory-Pattern））"><a href="#一、创建型模式（抽象工厂模式（Abstract-Factory-Pattern））" class="headerlink" title="一、创建型模式（抽象工厂模式（Abstract Factory Pattern））"></a>一、创建型模式（抽象工厂模式（Abstract Factory Pattern））</h1><h2 id="意图："><a href="#意图：" class="headerlink" title="意图："></a>意图：</h2><p>提供一个创建一系列相关或相互依赖对象的接口，而无需指定它们具体的类。</p>
<h2 id="主要解决："><a href="#主要解决：" class="headerlink" title="主要解决："></a>主要解决：</h2><p>主要解决接口选择的问题。</p>
<h2 id="何时使用："><a href="#何时使用：" class="headerlink" title="何时使用："></a>何时使用：</h2><p>系统的产品有多于一个的产品族，而系统只消费其中某一族的产品。</p>
<h2 id="创建步骤"><a href="#创建步骤" class="headerlink" title="创建步骤"></a>创建步骤</h2><h3 id="步骤一-创建一个接口"><a href="#步骤一-创建一个接口" class="headerlink" title="步骤一 创建一个接口"></a>步骤一 创建一个接口</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">class Shape</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	Shape() &#123;&#125;</span><br><span class="line">	virtual void draw()=0;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="步骤二-创建接口的实现类"><a href="#步骤二-创建接口的实现类" class="headerlink" title="步骤二 创建接口的实现类"></a>步骤二 创建接口的实现类</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">class Rectangle :public Shape</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	void draw()override</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;这是 Rectangle下的draw方法&quot;);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line">class Square :public Shape</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	void draw()override</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;这是 Square下的draw方法&quot;);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="步骤3-为颜色创建一个接口"><a href="#步骤3-为颜色创建一个接口" class="headerlink" title="步骤3 为颜色创建一个接口"></a>步骤3 为颜色创建一个接口</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">class Color</span><br><span class="line">&#123;public:</span><br><span class="line">	Color() &#123;&#125;;</span><br><span class="line">	virtual void fill() = 0;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="m步骤4-创建实现接口的实体类"><a href="#m步骤4-创建实现接口的实体类" class="headerlink" title="m步骤4 创建实现接口的实体类"></a>m步骤4 创建实现接口的实体类</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">class Red :public Color</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	void fill()override</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;这是 Red下的fill方法&quot;);</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;; </span><br><span class="line">class Blue :public Color</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	void fill()override</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;这是 Blue下的fill方法&quot;);</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;; </span><br><span class="line">class Green :public Color</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	void fill()override</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;这是 Green下的fill方法&quot;);</span><br><span class="line"></span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="步骤5-为Color与Shape对象创建抽象类来获取工厂"><a href="#步骤5-为Color与Shape对象创建抽象类来获取工厂" class="headerlink" title="步骤5 为Color与Shape对象创建抽象类来获取工厂"></a>步骤5 为Color与Shape对象创建抽象类来获取工厂</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">class AbFactory</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	virtual Color* getColor(char *color)=0;</span><br><span class="line">	virtual Shape* getShape(char *shape) =0;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="步骤6-创建实体的工厂类"><a href="#步骤6-创建实体的工厂类" class="headerlink" title="步骤6 创建实体的工厂类"></a>步骤6 创建实体的工厂类</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">class ShapeFactory :public AbFactory</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	Shape* getShape(char*shape)override</span><br><span class="line">	&#123;</span><br><span class="line">		if (shape == &quot;SQUARE&quot;)return new Square();</span><br><span class="line">		else if (shape == &quot;RECTANGLE&quot;)return new Rectangle();</span><br><span class="line">		return NULL;</span><br><span class="line">	&#125;</span><br><span class="line">	Color* getColor(char*color)override</span><br><span class="line">	&#123;</span><br><span class="line">		return NULL;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br><span class="line">class ColorFactory :public AbFactory</span><br><span class="line">&#123;</span><br><span class="line">public:</span><br><span class="line">	Shape* getShape(char*shape)override</span><br><span class="line">	&#123;</span><br><span class="line">		return NULL;</span><br><span class="line">	&#125;</span><br><span class="line">	Color* getColor(char*color)override</span><br><span class="line">	&#123;</span><br><span class="line">		if (color == &quot;RED&quot;)return new Red();</span><br><span class="line">		else if (color == &quot;GREEN&quot;)return new Green();</span><br><span class="line">		else if (color == &quot;BLUE&quot;)return new Blue();</span><br><span class="line"></span><br><span class="line">		return NULL;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h3 id="步骤7-创建一个工厂生成器，通过传递信息来获取工厂类"><a href="#步骤7-创建一个工厂生成器，通过传递信息来获取工厂类" class="headerlink" title="步骤7 创建一个工厂生成器，通过传递信息来获取工厂类"></a>步骤7 创建一个工厂生成器，通过传递信息来获取工厂类</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">class Producer</span><br><span class="line">&#123;public:</span><br><span class="line">	static AbFactory* getFactory(char* choice)</span><br><span class="line">	&#123;</span><br><span class="line">		if (choice == &quot;SHAPE&quot;)return new ShapeFactory();</span><br><span class="line">		else if (choice == &quot;COLOR&quot;)return new ColorFactory();</span><br><span class="line">		else return NULL;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/15/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/%E5%88%9B%E5%BB%BA%E5%9E%8B%E6%A8%A1%E5%BC%8F/%E6%8A%BD%E8%B1%A1%E5%B7%A5%E5%8E%82%E6%A8%A1%E5%BC%8F/" data-id="cl403sxss0058f8vu83zeb5j5" data-title="抽象工厂模式" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/1205-第二章线性表-习题总结" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/14/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1205-%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E4%B9%A0%E9%A2%98%E6%80%BB%E7%BB%93/" class="article-date">
  <time class="dt-published" datetime="2021-12-13T16:27:42.000Z" itemprop="datePublished">2021-12-14</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/14/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1205-%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E4%B9%A0%E9%A2%98%E6%80%BB%E7%BB%93/">1205 第二章线性表-习题总结</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="习题总结"><a href="#习题总结" class="headerlink" title="习题总结"></a>习题总结</h1><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">struct node</span><br><span class="line">&#123;</span><br><span class="line">	int data;</span><br><span class="line">	node* next;</span><br><span class="line">&#125;;</span><br><span class="line">struct List</span><br><span class="line">&#123;</span><br><span class="line">	node * head;</span><br><span class="line">	int length;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="1-从顺序表中删除具有最小值的元素，并由函数返回被删元素的值"><a href="#1-从顺序表中删除具有最小值的元素，并由函数返回被删元素的值" class="headerlink" title="1. 从顺序表中删除具有最小值的元素，并由函数返回被删元素的值"></a>1. 从顺序表中删除具有最小值的元素，并由函数返回被删元素的值</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">void RemoveList(int A[], int n,int solve)</span><br><span class="line">&#123;</span><br><span class="line">	if (n &lt;= 0) &#123;</span><br><span class="line">		printf(&quot;error&quot;); return;</span><br><span class="line">	&#125;</span><br><span class="line">	int m;</span><br><span class="line">	if (A[0] &gt; A[n - 1])</span><br><span class="line">	&#123;</span><br><span class="line">		m = A[n - 1];</span><br><span class="line">		A[n - 1] = A[n - 2];</span><br><span class="line">    &#125;</span><br><span class="line">	else</span><br><span class="line">	&#123;</span><br><span class="line">		m = A[0];</span><br><span class="line">		A[0] = A[n - 1];</span><br><span class="line">	&#125;</span><br><span class="line">	solve= m;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-设计算法-线性表逆置-空间复杂度O（1）"><a href="#2-设计算法-线性表逆置-空间复杂度O（1）" class="headerlink" title="2.设计算法 线性表逆置 空间复杂度O（1）"></a>2.设计算法 线性表逆置 空间复杂度O（1）</h2><h3 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h3><p>扫描线性表前半部分，将A[i]与A[n-i+1]进行交换</p>
<h3 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">void Reverse(int A[], int n)</span><br><span class="line">&#123;</span><br><span class="line">	for (int i = 0; i &lt; n / 2; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		int j = A[i];</span><br><span class="line">		A[i] = A[n - i + 1];</span><br><span class="line">		A[n - i + 1] = j;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="3-对长度为n的线性表L，删除线性表中所有值为x的数据元素"><a href="#3-对长度为n的线性表L，删除线性表中所有值为x的数据元素" class="headerlink" title="3.对长度为n的线性表L，删除线性表中所有值为x的数据元素"></a>3.对长度为n的线性表L，删除线性表中所有值为x的数据元素</h2><h3 id="代码-1"><a href="#代码-1" class="headerlink" title="代码"></a>代码</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">void  deleteList(int  A[], int n, int x)</span><br><span class="line">&#123;</span><br><span class="line">	if (n &lt;= 0)return;</span><br><span class="line">	int k = 0;//记录x的个数</span><br><span class="line">	for (int i = 0; i &lt; n; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		if (A[i] == x)</span><br><span class="line">			k++;</span><br><span class="line">		else</span><br><span class="line">			A[i - k] = A[i];</span><br><span class="line">	&#125;</span><br><span class="line">	for (int i = 0; i &lt; k; i++)</span><br><span class="line">		A[n - i - 1] = 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="4-从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s，t不合理或者顺序表为空，则显示错误信息并退出"><a href="#4-从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s，t不合理或者顺序表为空，则显示错误信息并退出" class="headerlink" title="4.从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s，t不合理或者顺序表为空，则显示错误信息并退出"></a>4.从有序顺序表中删除其值在给定值s与t之间的所有元素，如果s，t不合理或者顺序表为空，则显示错误信息并退出</h2><h3 id="思想"><a href="#思想" class="headerlink" title="思想"></a>思想</h3><p>由于有序表，所以找到最小的元素(大于s)将后续元素体前就行了</p>
<h3 id="代码-2"><a href="#代码-2" class="headerlink" title="代码"></a>代码</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">由于有序表，所以找到最小的元素(大于s)将后续元素体前就行了</span><br></pre></td></tr></table></figure>
<ol>
<li>从有序表中删除所有值重复的元素，使元素不重复</li>
</ol>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/14/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1205-%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E4%B9%A0%E9%A2%98%E6%80%BB%E7%BB%93/" data-id="cl403sxs7003ef8vu0ijecddf" data-title="1205 第二章线性表-习题总结" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/1801 第八章 图 图算法" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/13/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1801%20%E7%AC%AC%E5%85%AB%E7%AB%A0%20%E5%9B%BE%20%E5%9B%BE%E7%AE%97%E6%B3%95/" class="article-date">
  <time class="dt-published" datetime="2021-12-13T06:46:54.000Z" itemprop="datePublished">2021-12-13</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/13/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1801%20%E7%AC%AC%E5%85%AB%E7%AB%A0%20%E5%9B%BE%20%E5%9B%BE%E7%AE%97%E6%B3%95/">图算法</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、图需要的宏定义"><a href="#一、图需要的宏定义" class="headerlink" title="一、图需要的宏定义"></a>一、图需要的宏定义</h1><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">#define MAX_LIST 15</span><br><span class="line">#define INFINITE 1000000</span><br><span class="line">#define MAX_LINE 1024</span><br></pre></td></tr></table></figure>
<h1 id="二、图的表结构"><a href="#二、图的表结构" class="headerlink" title="二、图的表结构"></a>二、图的表结构</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">int</span> id;</span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">char</span> name[<span class="number">10</span>];<span class="comment">//景点名称</span></span><br><span class="line">    <span class="keyword">unsigned</span> <span class="keyword">char</span> intro[<span class="number">10</span>];</span><br><span class="line">&#125;Tourist;</span><br><span class="line">Tourist tourist[MAX_LIST];</span><br><span class="line"><span class="keyword">int</span> num=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">int</span> list[MAX_LIST];</span><br><span class="line">	<span class="keyword">int</span> size;</span><br><span class="line">&#125;SeqList;</span><br><span class="line">SeqList seq;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line">    <span class="keyword">int</span> vexs[MAX_LIST];                  <span class="comment">//顶点</span></span><br><span class="line">    <span class="keyword">int</span>        arcs[MAX_LIST][MAX_LIST];  <span class="comment">//边</span></span><br><span class="line">    <span class="keyword">int</span>        vexnum, arcnum;</span><br><span class="line">&#125;MGraph;</span><br><span class="line">MGraph g;</span><br><span class="line"><span class="comment">//辅助数组中的元素定义 </span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> distance;</span><br><span class="line">    <span class="keyword">int</span> path[MAX_LIST];</span><br><span class="line">&#125;ArrayNode;</span><br><span class="line"></span><br><span class="line"><span class="keyword">unsigned</span> <span class="keyword">char</span> *msg[MAX_LIST] = &#123; (<span class="keyword">unsigned</span> <span class="keyword">char</span>*)<span class="string">&quot;体育馆1\0\0&quot;</span>,(<span class="keyword">unsigned</span> <span class="keyword">char</span>*)<span class="string">&quot;体育馆2\0\0&quot;</span>,(<span class="keyword">unsigned</span> <span class="keyword">char</span>*)<span class="string">&quot;体育馆3\0\0&quot;</span>,(<span class="keyword">unsigned</span> <span class="keyword">char</span>*)<span class="string">&quot;体育馆4\0\0&quot;</span>,(<span class="keyword">unsigned</span> <span class="keyword">char</span>*)<span class="string">&quot;体育馆5\0\0&quot;</span> &#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> pathOrder = <span class="number">0</span>;  <span class="comment">//记录到当前找到的路径个数 </span></span><br><span class="line"><span class="keyword">int</span> startPoint, endPoint;</span><br><span class="line"><span class="keyword">int</span> path[<span class="number">100</span>], visited[<span class="number">100</span>] = &#123; <span class="number">0</span> &#125;;</span><br><span class="line"><span class="keyword">int</span> pathNumber = <span class="number">0</span>;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MaxVertexNum 100</span></span><br><span class="line"><span class="comment">//O(n^2)</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">char</span> vex[MaxVertexNum];</span><br><span class="line">	<span class="keyword">int</span> edge[MaxVertexNum][MaxVertexNum];</span><br><span class="line">	<span class="keyword">int</span> vexnum, arcnum;</span><br><span class="line">&#125;MGragh;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">///</span></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">G 无向图  存储空间：O(|V|+2|E|)</span></span><br><span class="line"><span class="comment">  有向图  存储空间：O(|V|+|E|)</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">arcNode</span>;</span></span><br><span class="line"><span class="comment">//定点表</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">char</span> data;</span><br><span class="line">	arcNode* first;</span><br><span class="line">&#125;VNode,AdjList[MaxVertexNum];</span><br><span class="line"><span class="comment">//边节点</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">int</span> adjvex;</span><br><span class="line">	arcNode *next;</span><br><span class="line">	<span class="keyword">int</span> length;</span><br><span class="line">&#125;arcNode;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	AdjList vetice;</span><br><span class="line">	<span class="keyword">int</span> vexnum, arcnum;</span><br><span class="line">&#125;MGragh2;</span><br></pre></td></tr></table></figure>
<h1 id="三、图的操作"><a href="#三、图的操作" class="headerlink" title="三、图的操作"></a>三、图的操作</h1><h2 id="3-1-图的初始化"><a href="#3-1-图的初始化" class="headerlink" title="3.1 图的初始化"></a>3.1 图的初始化</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line">void Init()</span><br><span class="line">&#123;</span><br><span class="line">    for (int i = 0; i &lt; MAX_LIST; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        for (int j = 0; j &lt; MAX_LIST; j++)</span><br><span class="line">        &#123;</span><br><span class="line">            g.arcs[i][j] = INFINITE;</span><br><span class="line">        &#125;</span><br><span class="line">        g.vexs[i] = -1;</span><br><span class="line">    &#125;</span><br><span class="line">    g.arcnum = 0;</span><br><span class="line">    g.vexnum = 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br></pre></td><td class="code"><pre><span class="line">void InsertList(int i)</span><br><span class="line">&#123;</span><br><span class="line">	if (seq.size &lt; MAX_LIST)</span><br><span class="line">	&#123;</span><br><span class="line">		seq.list[seq.size]=i;</span><br><span class="line">		seq.size++;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">int GetListnum()</span><br><span class="line">&#123;</span><br><span class="line">	return seq.size;</span><br><span class="line">&#125;</span><br><span class="line">void DeleteList(int i)</span><br><span class="line">&#123;</span><br><span class="line">	if (i &gt;= 0 &amp;&amp; i &lt; MAX_LIST)</span><br><span class="line">	&#123;</span><br><span class="line">		for (int j = i + 1; j &lt; seq.size; j++)</span><br><span class="line">		&#123;</span><br><span class="line">			seq.list[j] = seq.list[j + 1];</span><br><span class="line">		&#125;</span><br><span class="line">		seq.size--;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">int GetList(int i)</span><br><span class="line">&#123;</span><br><span class="line">	return seq.list[i];</span><br><span class="line">&#125;</span><br><span class="line">//添加景点信息</span><br><span class="line">void InsertTour(int id,char name[10],char intro[10])</span><br><span class="line">&#123;</span><br><span class="line">	tourist[num].id = id;</span><br><span class="line">	strcpy(tourist[num].name , name);</span><br><span class="line">	strcpy(tourist[num].intro , intro);</span><br><span class="line">	num++;</span><br><span class="line">&#125;</span><br><span class="line">//添加顶点</span><br><span class="line">void insertVex(int id, char name[10], char intro[10])</span><br><span class="line">&#123;</span><br><span class="line">    InsertTour(id, name, intro);</span><br><span class="line">    g.vexs[g.vexnum] = id;</span><br><span class="line">    g.vexnum++;</span><br><span class="line">&#125;</span><br><span class="line">//添加边</span><br><span class="line">void insertarc(int a,int b,int length)</span><br><span class="line">&#123;</span><br><span class="line">    g.arcs[a][b] = length;</span><br><span class="line">    g.arcs[b][a] = length;</span><br><span class="line">    g.arcnum++;</span><br><span class="line">&#125;</span><br><span class="line">//更新路径长度</span><br><span class="line">void UpdataLoadLength(int a, int b, int length)</span><br><span class="line">&#123;</span><br><span class="line">    g.arcs[a][b] = length;</span><br><span class="line">    g.arcs[b][a] = length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">void Reads()</span><br><span class="line">&#123;</span><br><span class="line">	int d=setlocale(0, &quot;chs&quot;);</span><br><span class="line">	//下面是读数据，将读到的数据存到数组a[10]中，并且打印到控制台上</span><br><span class="line">	FILE* fpRead = fopen(&quot;1.txt&quot;, &quot;r&quot;);</span><br><span class="line">	if (fpRead == NULL)</span><br><span class="line">	&#123;</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">	int n;</span><br><span class="line">	int error=fscanf(fpRead, &quot;%d&quot;, &amp;n);</span><br><span class="line">	Init();</span><br><span class="line">	for (int i = 0; i &lt; n; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		int id;</span><br><span class="line">        unsigned char name[10];</span><br><span class="line">        unsigned char intro[10];</span><br><span class="line">		int error = fscanf(fpRead, &quot;%d %s %s&quot;, &amp;id, &amp;name, &amp;intro);</span><br><span class="line">        strcpy( name,msg[i] );</span><br><span class="line">		InsertList(id);</span><br><span class="line">		insertVex(id, name, intro);</span><br><span class="line">	&#125;</span><br><span class="line">	for (int i = 0; i &lt; 6; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		int a, b, length;</span><br><span class="line">		int mm=fscanf(fpRead, &quot;%d %d %d&quot;, &amp;a, &amp;b, &amp;length);</span><br><span class="line">		insertarc(a-1, b-1, length);</span><br><span class="line">	&#125;	</span><br><span class="line">	int cc=fclose(fpRead);</span><br><span class="line">&#125;</span><br><span class="line">//迪杰斯特拉算法---解决最短路径问题</span><br><span class="line">void Dijkstra(int from, int to)</span><br><span class="line">&#123;</span><br><span class="line">    int i, j, index = -1;</span><br><span class="line">    int n = 1;//记录已经求出的两个点之间的最短距离的个数 </span><br><span class="line">    ArrayNode shortestPath[MAX_LIST];</span><br><span class="line">    int flag[MAX_LIST] = &#123; 0 &#125;;//标记，为1表示到这个顶点的最短距离已求出 </span><br><span class="line"></span><br><span class="line">    //1.求from到各个顶点的直接距离，即初始化shortestPath数组 </span><br><span class="line">    for (i = 0; i &lt; g.vexnum; i++) &#123;</span><br><span class="line">        if (from == i) &#123;</span><br><span class="line">            shortestPath[i].distance = 0;</span><br><span class="line">            shortestPath[i].path[0] = i;</span><br><span class="line">            flag[from] = 1;</span><br><span class="line">        &#125;</span><br><span class="line">        else if (g.arcs[from][i] &gt; 0) &#123;</span><br><span class="line">            shortestPath[i].path[0] = from;</span><br><span class="line">            shortestPath[i].path[1] = i;</span><br><span class="line">            shortestPath[i].distance = g.arcs[from][i];</span><br><span class="line">        &#125;</span><br><span class="line">        else</span><br><span class="line">            shortestPath[i].distance = INFINITE;</span><br><span class="line">    &#125;</span><br><span class="line">    //2.每次求一个最短路径 </span><br><span class="line">    while (n &lt; g.vexnum) &#123;</span><br><span class="line">        //选择shortestPath中距离最小的，求出from到这个顶点的最短路径 </span><br><span class="line">        index = -1;</span><br><span class="line">        for (i = 0; i &lt; g.vexnum; i++) &#123;</span><br><span class="line">            if (i == from)</span><br><span class="line">                continue;</span><br><span class="line">            if (flag[i] == 0 &amp;&amp; index == -1 &amp;&amp; shortestPath[i].distance != INFINITE)</span><br><span class="line">                index = i;</span><br><span class="line">            if (flag[i] == 0 &amp;&amp; index != -1 &amp;&amp; shortestPath[i].distance &lt; shortestPath[index].distance)</span><br><span class="line">                index = i;</span><br><span class="line">        &#125;</span><br><span class="line">        flag[index] = 1;</span><br><span class="line">        //修改到各个顶点的最短路径 </span><br><span class="line">        for (i = 0; i &lt; g.vexnum; i++) &#123;</span><br><span class="line">            if (i == from)</span><br><span class="line">                continue;</span><br><span class="line">            if (g.arcs[index][i] &gt; 0 &amp;&amp; g.arcs[index][i] + shortestPath[index].distance &lt; shortestPath[i].distance) &#123;</span><br><span class="line">                shortestPath[i].distance = g.arcs[index][i] + shortestPath[index].distance;</span><br><span class="line">                //修改路径 </span><br><span class="line">                j = 0;</span><br><span class="line">                while (1) &#123;</span><br><span class="line">                    shortestPath[i].path[j] = shortestPath[index].path[j];</span><br><span class="line">                    if (shortestPath[index].path[j] == index)</span><br><span class="line">                        break;</span><br><span class="line">                    j++;</span><br><span class="line">                &#125;</span><br><span class="line">                shortestPath[i].path[j + 1] = i;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        n++;</span><br><span class="line">    &#125;</span><br><span class="line">    //输出from到to的最短路径及长度 </span><br><span class="line">    if (shortestPath[to].distance == INFINITE) &#123;</span><br><span class="line">        printf(&quot;%s到%s没有路径\n&quot;, tourist[from].name, tourist[to].name);</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%s到%s的最短路径长度是：%d\n&quot;, tourist[from].name, tourist[to].name, shortestPath[to].distance);</span><br><span class="line">    printf(&quot;经过的地址是：  &quot;);</span><br><span class="line">    i = 0;</span><br><span class="line">    while (1) &#123;</span><br><span class="line">        printf(&quot;-%s&quot;, tourist[shortestPath[to].path[i]].name);</span><br><span class="line">        if (shortestPath[to].path[i] == to)</span><br><span class="line">            break;</span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;\n&quot;);</span><br><span class="line">&#125;</span><br><span class="line">//解决所有路径问题</span><br><span class="line">int first(int n)</span><br><span class="line">&#123;</span><br><span class="line">    for (int i = 0; i &lt; g.vexnum; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        if (g.arcs[n][i] != INFINITE&amp;&amp;n!=i)</span><br><span class="line">            return i;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;起点为故障点，请输入一个不为故障点的起点\n&quot;);</span><br><span class="line">    return 1000;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int sumCount(int n)</span><br><span class="line">&#123;</span><br><span class="line">    int count = 0;</span><br><span class="line">    for (int i = 0; i &lt; g.vexnum; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        if (g.arcs[n][i] == INFINITE)</span><br><span class="line">            count++;</span><br><span class="line">    &#125;</span><br><span class="line">    return count;</span><br><span class="line">&#125;</span><br><span class="line">int next(int n, int now)</span><br><span class="line">&#123;</span><br><span class="line">    for (int i = now + 1; i &lt; g.vexnum; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        if (g.arcs[n][i] != INFINITE)</span><br><span class="line">            return i;</span><br><span class="line">    &#125;</span><br><span class="line">    return 1000;  //当找不到节点n的下一个节点，返回1000</span><br><span class="line">&#125;</span><br><span class="line">void DFS(int nowPoint, int count)</span><br><span class="line">&#123;</span><br><span class="line">    visited[nowPoint] = 1;</span><br><span class="line">    path[count++] = nowPoint;</span><br><span class="line">    if (nowPoint == endPoint &amp;&amp; (count) &gt;= 1)</span><br><span class="line">    &#123;</span><br><span class="line">        pathNumber++;</span><br><span class="line">        printf(&quot;这两个地址间第%d条路径为: &quot;, pathNumber);</span><br><span class="line">        for (int i = 0; i &lt; (count)-1; i++)</span><br><span class="line">        &#123;</span><br><span class="line">            printf(&quot;%d--&gt;&quot;, path[i] + 1);</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;%d\n&quot;, path[(count)-1] + 1);</span><br><span class="line">    &#125;</span><br><span class="line">    else</span><br><span class="line">    &#123;</span><br><span class="line">        int k;</span><br><span class="line">        for (k = first(nowPoint); k &lt; g.vexnum; k = next(nowPoint, k))</span><br><span class="line">        &#123;</span><br><span class="line">            if (visited[k] == 0)</span><br><span class="line">                DFS(k, count);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    visited[nowPoint] = 0;  //算法关键，回溯，将访问过状态变为未访问状态 </span><br><span class="line">    (count)--;</span><br><span class="line">    return;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/13/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1801%20%E7%AC%AC%E5%85%AB%E7%AB%A0%20%E5%9B%BE%20%E5%9B%BE%E7%AE%97%E6%B3%95/" data-id="cl403sxs8003if8vugw9c009c" data-title="图算法" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/1201 第二章线性表-定义" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1201%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E5%AE%9A%E4%B9%89/" class="article-date">
  <time class="dt-published" datetime="2021-12-12T06:46:54.000Z" itemprop="datePublished">2021-12-12</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1201%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E5%AE%9A%E4%B9%89/">链表</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、线性表的定义"><a href="#一、线性表的定义" class="headerlink" title="一、线性表的定义"></a>一、线性表的定义</h1><p>具有相同数据类型的n个数据元素的有限序列<br>其中n是表长<br>用L命名线性表  表示为  L=(a1,a2,a3,……,an)<br>直接前驱直接后继</p>
<h1 id="二、线性表的性质"><a href="#二、线性表的性质" class="headerlink" title="二、线性表的性质"></a>二、线性表的性质</h1><p>1.表中元素有限<br>2.表中元素具有逻辑上的顺序性<br>3.表中元素都是数据元素，每个元素都是单个元素<br>4.表中元素数据类型都相同，有相同的存储空间<br>5.表中元素具有抽象性</p>
<h1 id="三、线性表的基本操作"><a href="#三、线性表的基本操作" class="headerlink" title="三、线性表的基本操作"></a>三、线性表的基本操作</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LinkList</span>;</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">InitList</span><span class="params">(LinkList&amp;L)</span></span>;<span class="comment">//初始化表</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListLength</span><span class="params">(<span class="keyword">const</span> LinkList&amp;L)</span></span>;<span class="comment">//求表长</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">LocateElem</span><span class="params">(LinkList&amp;L,<span class="keyword">int</span> e)</span></span>;<span class="comment">//按值查找操作</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">GetElem</span><span class="params">(LinkList&amp;L,<span class="keyword">int</span> i)</span></span>;<span class="comment">//按位查找操作</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">ListInsert</span><span class="params">(LinkList&amp;L,<span class="keyword">int</span> i,<span class="keyword">int</span> e)</span></span>;<span class="comment">//插入</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">ListDelete</span><span class="params">(LinkList&amp;L,<span class="keyword">int</span> i ,<span class="keyword">int</span>&amp;e)</span></span>;<span class="comment">//删除第i位元素</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">PrintList</span><span class="params">(<span class="keyword">const</span> LinkList&amp;L)</span></span>;<span class="comment">//打印表</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Empty</span><span class="params">(LinkList&amp;L)</span></span>;<span class="comment">//判空</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">DestoryList</span><span class="params">(LinkList&amp;L)</span></span>;<span class="comment">//销毁表</span></span><br></pre></td></tr></table></figure>
<h2 id="3-1-存储结构的顺序表示"><a href="#3-1-存储结构的顺序表示" class="headerlink" title="3.1 存储结构的顺序表示"></a>3.1 存储结构的顺序表示</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">struct LinkList</span><br><span class="line">&#123;</span><br><span class="line">	int *data;//顺序表中的元素</span><br><span class="line">	int length;//当前长度</span><br><span class="line">    const int maxLength=10;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="3-2-初始化表"><a href="#3-2-初始化表" class="headerlink" title="3.2 初始化表"></a>3.2 初始化表</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">void InitList(LinkList&amp;L)</span><br><span class="line">&#123;</span><br><span class="line">	int InitSize = 10;</span><br><span class="line">	L.data = new int[InitSize];</span><br><span class="line">	//L.data = (int*)malloc(sizeof(int)*InitSize);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="3-3-线性表的插入"><a href="#3-3-线性表的插入" class="headerlink" title="3.3 线性表的插入"></a>3.3 线性表的插入</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">bool ListInsert(LinkList&amp;L, int i, int e)//插入</span><br><span class="line">&#123;</span><br><span class="line">	if (i&lt;1 || i&gt;L.length + 1)</span><br><span class="line">		return false;</span><br><span class="line">	if (i &gt;= L.maxLength)</span><br><span class="line">		return false;</span><br><span class="line">	for (auto j = L.length; j &gt;= i; j++)</span><br><span class="line">		L.data[j] = L.data[j - 1];</span><br><span class="line">	L.data[i - 1] = e;</span><br><span class="line">	L.length++;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="3-4-线性表的删除"><a href="#3-4-线性表的删除" class="headerlink" title="3.4 线性表的删除"></a>3.4 线性表的删除</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">bool ListDelete(LinkList&amp;L, int i, int&amp;e)//删除第i位元素</span><br><span class="line">&#123;</span><br><span class="line">	if (i &lt; 1 || i &gt;= L.length)return false;</span><br><span class="line">	e = L.data[i - 1];</span><br><span class="line"></span><br><span class="line">	for (int i = 0; i &lt; L.length; i++)</span><br><span class="line">		L.data[i - 1] = L.data[i];</span><br><span class="line">	L.length--;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ListNode</span> &#123;</span></span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">ListNode</span>* <span class="title">next</span>;</span></span><br><span class="line">    <span class="built_in">ListNode</span>(<span class="keyword">int</span> x) :</span><br><span class="line">        <span class="built_in">val</span>(x), <span class="built_in">next</span>(<span class="literal">nullptr</span>) &#123;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h1 id="二、链表的操作"><a href="#二、链表的操作" class="headerlink" title="二、链表的操作"></a>二、链表的操作</h1><h2 id="2-1-获取链表的长度"><a href="#2-1-获取链表的长度" class="headerlink" title="2.1 获取链表的长度"></a>2.1 获取链表的长度</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListLength</span><span class="params">(ListNode* node)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (node != <span class="literal">nullptr</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        n++;</span><br><span class="line">        node = node-&gt;next;</span><br><span class="line">    &#125;<span class="keyword">return</span> n;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="2-3-查找第k位置的值"><a href="#2-3-查找第k位置的值" class="headerlink" title="2.3 查找第k位置的值"></a>2.3 查找第k位置的值</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ListNode* <span class="title">FindKthToTail</span><span class="params">(ListNode* pListHead, <span class="keyword">unsigned</span> <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = <span class="built_in">ListLength</span>(pListHead);</span><br><span class="line">    length -= k;</span><br><span class="line">    <span class="keyword">if</span> (length &lt; <span class="number">0</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">while</span> (length--&gt;<span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        pListHead = pListHead-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pListHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-4-输入一个链表，反转链表后，输出新链表的表头"><a href="#2-4-输入一个链表，反转链表后，输出新链表的表头" class="headerlink" title="2.4 输入一个链表，反转链表后，输出新链表的表头"></a>2.4 输入一个链表，反转链表后，输出新链表的表头</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ListNode* <span class="title">ReverseList</span><span class="params">(ListNode* pHead)</span> </span>&#123;</span><br><span class="line">    ListNode* c = pHead,*d;</span><br><span class="line">    <span class="keyword">if</span> (pHead == <span class="literal">nullptr</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">if</span> (pHead-&gt;next == <span class="literal">nullptr</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    d = pHead-&gt;next;</span><br><span class="line">    <span class="keyword">while</span> (d != <span class="literal">nullptr</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        d-&gt;next = c;</span><br><span class="line">        c = d;</span><br><span class="line">        d = c-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="2-1-输入一个链表，按链表从尾到头的顺序返回一个ArrayList"><a href="#2-1-输入一个链表，按链表从尾到头的顺序返回一个ArrayList" class="headerlink" title="2.1 输入一个链表，按链表从尾到头的顺序返回一个ArrayList"></a>2.1 输入一个链表，按链表从尾到头的顺序返回一个ArrayList</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;int&gt; printListFromTailToHead(ListNode* head) &#123;</span><br><span class="line">    vector&lt;int&gt;f;</span><br><span class="line">    stack&lt;int&gt;c;</span><br><span class="line">    while (head != nullptr)</span><br><span class="line">    &#123;</span><br><span class="line">        c.push(head-&gt;val);</span><br><span class="line">        head = head-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    while (c.size() &gt; 0)</span><br><span class="line">    &#123;</span><br><span class="line">        f.push_back(c.top());</span><br><span class="line">        c.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    return f;</span><br><span class="line">&#125;;   </span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1201%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E5%AE%9A%E4%B9%89/" data-id="cl403sxs6003df8vufnlbhe67" data-title="链表" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/1203 第二章线性表-链表" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1203%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E9%93%BE%E8%A1%A8/" class="article-date">
  <time class="dt-published" datetime="2021-12-12T06:46:54.000Z" itemprop="datePublished">2021-12-12</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1203%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E9%93%BE%E8%A1%A8/">第二章线性表-链表</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、链表的结构"><a href="#一、链表的结构" class="headerlink" title="一、链表的结构"></a>一、链表的结构</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ListNode</span> &#123;</span></span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">ListNode</span>* <span class="title">next</span>;</span></span><br><span class="line">    <span class="built_in">ListNode</span>(<span class="keyword">int</span> x) :</span><br><span class="line">        <span class="built_in">val</span>(x), <span class="built_in">next</span>(<span class="literal">nullptr</span>) &#123;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h1 id="二、链表的操作"><a href="#二、链表的操作" class="headerlink" title="二、链表的操作"></a>二、链表的操作</h1><h2 id="2-1-获取链表的长度"><a href="#2-1-获取链表的长度" class="headerlink" title="2.1 获取链表的长度"></a>2.1 获取链表的长度</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListLength</span><span class="params">(ListNode* node)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (node != <span class="literal">nullptr</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        n++;</span><br><span class="line">        node = node-&gt;next;</span><br><span class="line">    &#125;<span class="keyword">return</span> n;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="2-3-查找第k位置的值"><a href="#2-3-查找第k位置的值" class="headerlink" title="2.3 查找第k位置的值"></a>2.3 查找第k位置的值</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ListNode* <span class="title">FindKthToTail</span><span class="params">(ListNode* pListHead, <span class="keyword">unsigned</span> <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">int</span> length = <span class="built_in">ListLength</span>(pListHead);</span><br><span class="line">    length -= k;</span><br><span class="line">    <span class="keyword">if</span> (length &lt; <span class="number">0</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">while</span> (length--&gt;<span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        pListHead = pListHead-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pListHead;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-4-输入一个链表，反转链表后，输出新链表的表头"><a href="#2-4-输入一个链表，反转链表后，输出新链表的表头" class="headerlink" title="2.4 输入一个链表，反转链表后，输出新链表的表头"></a>2.4 输入一个链表，反转链表后，输出新链表的表头</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ListNode* <span class="title">ReverseList</span><span class="params">(ListNode* pHead)</span> </span>&#123;</span><br><span class="line">    ListNode* c = pHead,*d;</span><br><span class="line">    <span class="keyword">if</span> (pHead == <span class="literal">nullptr</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">if</span> (pHead-&gt;next == <span class="literal">nullptr</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    d = pHead-&gt;next;</span><br><span class="line">    <span class="keyword">while</span> (d != <span class="literal">nullptr</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        d-&gt;next = c;</span><br><span class="line">        c = d;</span><br><span class="line">        d = c-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-5-显示单链表所有元素"><a href="#2-5-显示单链表所有元素" class="headerlink" title="2.5 显示单链表所有元素"></a>2.5 显示单链表所有元素</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListPrint</span><span class="params">(LinkList &amp;L)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">auto</span> i = L.begin; i != L.end; i = i-&gt;next)</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>, i-&gt;data);</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="2-6-将存放于单链表中的所有字母均前移n个位置"><a href="#2-6-将存放于单链表中的所有字母均前移n个位置" class="headerlink" title="2.6 将存放于单链表中的所有字母均前移n个位置"></a>2.6 将存放于单链表中的所有字母均前移n个位置</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">EncryptList</span><span class="params">(LinkList &amp;L, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">		<span class="built_in">PushList</span>(L, <span class="built_in">PopList</span>(L));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-7-逆序建立一个（带有头结点的）单链表。即，在键盘上按顺序输入26个大写英文字母A……Z，最后输入的字母Z，放在头结点之后；第一个输入的字母A放在单链表的末尾。"><a href="#2-7-逆序建立一个（带有头结点的）单链表。即，在键盘上按顺序输入26个大写英文字母A……Z，最后输入的字母Z，放在头结点之后；第一个输入的字母A放在单链表的末尾。" class="headerlink" title="2.7 逆序建立一个（带有头结点的）单链表。即，在键盘上按顺序输入26个大写英文字母A……Z，最后输入的字母Z，放在头结点之后；第一个输入的字母A放在单链表的末尾。"></a>2.7 逆序建立一个（带有头结点的）单链表。即，在键盘上按顺序输入26个大写英文字母A……Z，最后输入的字母Z，放在头结点之后；第一个输入的字母A放在单链表的末尾。</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">CreateList</span><span class="params">(LinkList &amp;L, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">char</span> c;</span><br><span class="line">		<span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>, &amp;c);</span><br><span class="line">		<span class="built_in">PushList</span>(L, c);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-8删除前一个节点"><a href="#2-8删除前一个节点" class="headerlink" title="2.8删除前一个节点"></a>2.8删除前一个节点</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">char</span> <span class="title">PopList</span><span class="params">(LinkList&amp;L)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span> (L.begin == L.end) &#123; <span class="built_in">printf</span>(<span class="string">&quot;栈空错误&quot;</span>); <span class="keyword">return</span> <span class="string">&#x27;\0&#x27;</span>; &#125;</span><br><span class="line">	<span class="keyword">char</span> c = L.begin-&gt;data;</span><br><span class="line">	<span class="keyword">auto</span> i = L.begin-&gt;next;</span><br><span class="line">	<span class="keyword">delete</span> i-&gt;parent;</span><br><span class="line">	L.begin = i;</span><br><span class="line">	<span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-1-输入一个链表，按链表从尾到头的顺序返回一个ArrayList"><a href="#2-1-输入一个链表，按链表从尾到头的顺序返回一个ArrayList" class="headerlink" title="2.1 输入一个链表，按链表从尾到头的顺序返回一个ArrayList"></a>2.1 输入一个链表，按链表从尾到头的顺序返回一个ArrayList</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">printListFromTailToHead</span><span class="params">(ListNode* head)</span> </span>&#123;</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt;f;</span><br><span class="line">    stack&lt;<span class="keyword">int</span>&gt;c;</span><br><span class="line">    <span class="keyword">while</span> (head != <span class="literal">nullptr</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        c.<span class="built_in">push</span>(head-&gt;val);</span><br><span class="line">        head = head-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (c.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        f.<span class="built_in">push_back</span>(c.<span class="built_in">top</span>());</span><br><span class="line">        c.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> f;</span><br><span class="line">&#125;;   </span><br></pre></td></tr></table></figure>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1203%20%E7%AC%AC%E4%BA%8C%E7%AB%A0%E7%BA%BF%E6%80%A7%E8%A1%A8-%E9%93%BE%E8%A1%A8/" data-id="cl403sxs7003gf8vueiil72d4" data-title="第二章线性表-链表" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/1701 第七章 树 二叉树" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/" class="article-date">
  <time class="dt-published" datetime="2021-12-12T06:46:54.000Z" itemprop="datePublished">2021-12-12</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/">二叉树</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="一、二叉树的结构"><a href="#一、二叉树的结构" class="headerlink" title="一、二叉树的结构"></a>一、二叉树的结构</h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">TreeNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> val;</span><br><span class="line">    TreeNode* parent;</span><br><span class="line">    TreeNode* left;</span><br><span class="line">    TreeNode* right;</span><br><span class="line">    <span class="built_in">TreeNode</span>(<span class="keyword">int</span> x) : <span class="built_in">val</span>(x), <span class="built_in">parent</span>(<span class="literal">NULL</span>), <span class="built_in">left</span>(<span class="literal">NULL</span>), <span class="built_in">right</span>(<span class="literal">NULL</span>) &#123;&#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<h2 id="树的性质"><a href="#树的性质" class="headerlink" title="树的性质"></a>树的性质</h2><ul>
<li>树具有如下最基本的性质:<script type="math/tex; mode=display">
\text{1)树中的结点数等于所有结点的度数加l。}\\
\text{2)度为m的树中第i层上至多有}m^{i-1}\text{个结点(i≥1)}。\\
\text{3)高度为h的m叉树至多有}\frac{m^h-1}{m-1} \text{个结点}\\
\text{4)具有n个结点的m义树的最小高度为}\log_{m}{(n(m-1)+1)}</script></li>
</ul>
<p>”。γP深度乙差不超过1。<br>3.<br>二叉树的性质<br>非空二叉树 上的叶子结点数等于度为2的结点数加，即no=m2+1。<br>证明:<br>设度为0、1和2的结点个数分别为no. n和n2:结点总数n=<br>no+n +n2.<br>再着二又树中的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，<br>则n=B+</p>
<ol>
<li>由于这些分支是由度为1或2的结点射出的，所以又有B=n+2ng.<br>于是得no<br>+n+n2=n+2n2+ 1，则no=n2+1.<br>注意:<br>该结论经常在选择题中用到，希望考生牢记并灵活应用。<br>，空二叉树上第大层上至名有2-个结点(k3D.<br>高度为力的又树年名行2” !个结点(h21)。<br>3)<br>时完个二叉树按从上:到下、从左到右的顺序依次编号12..n则有以下关系:<br>4)<br>对1&gt; 1时，结点i的双亲结点编号xLi2J,即当i为偶数时，其双亲结点的编号为12.<br>它是双亲结点的左孩子:当i为奇数时，其双亲结点的编号为(- 1)12, 它是双亲结点<br>的右孩子。<br>2的1≤n时，结点的左孩子编号为2.在则无左孩子。<br>当241时，结点:的右孩子编号为21+1.1否则无右孩子。<br>国结点:所在层次(深度)为Lg;iti<br>3)具有n个(n&gt;0)结点的完全二<br>.叉树的高度为[log:(n+ 11或LogunI+ 1。</li>
</ol>
<h1 id="二、二叉树的操作"><a href="#二、二叉树的操作" class="headerlink" title="二、二叉树的操作"></a>二、二叉树的操作</h1><h2 id="2-1-先序遍历-中序遍历构建二叉树"><a href="#2-1-先序遍历-中序遍历构建二叉树" class="headerlink" title="2.1 先序遍历+中序遍历构建二叉树"></a>2.1 先序遍历+中序遍历构建二叉树</h2><ul>
<li>先序遍历（PreOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)访问根结点;</li>
<li>2）先序遍历左子树;</li>
<li>3）先序遍历右子树。</li>
</ul>
</li>
<li>中序遍历（InOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)中序遍历左子树;</li>
<li>2)访问根结点;</li>
<li>3)中序遍历右子树。对应的递归算法如下:</li>
</ul>
</li>
<li>后序遍历（PostOrder）的操作过程如下:若二叉树为空，则什么也不做;否则,<ul>
<li>1)后序遍历左子树;</li>
<li>2)后序遍历右子树;</li>
<li>3)访问根结点。<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">reConstructBinaryTree</span><span class="params">(TreeNode* node, vector&lt;<span class="keyword">int</span>&gt; pre, vector&lt;<span class="keyword">int</span>&gt; vin)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (pre.<span class="built_in">size</span>() &lt; <span class="number">1</span>)<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> c = pre[<span class="number">0</span>];</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; vin2;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; vin3;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; pre2;</span><br><span class="line">        vector&lt;<span class="keyword">int</span>&gt; pre3;</span><br><span class="line">        <span class="keyword">bool</span> ispre = <span class="literal">false</span>;</span><br><span class="line">        <span class="keyword">int</span> j = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; vin.<span class="built_in">size</span>(); i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (vin[i] == c) &#123; ispre = <span class="literal">true</span>; <span class="keyword">continue</span>; &#125;</span><br><span class="line">            <span class="keyword">if</span> (ispre == <span class="literal">false</span>) &#123; vin2.<span class="built_in">push_back</span>(vin[i]); pre2.<span class="built_in">push_back</span>(pre[j]); j++; &#125;</span><br><span class="line">            <span class="keyword">if</span> (ispre == <span class="literal">true</span>) &#123; vin3.<span class="built_in">push_back</span>(vin[i]); pre3.<span class="built_in">push_back</span>(pre[j]); j++; &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        node = <span class="keyword">new</span> <span class="built_in">TreeNode</span>(pre[<span class="number">0</span>]);</span><br><span class="line"></span><br><span class="line">        node-&gt;left = <span class="built_in">reConstructBinaryTree</span>(node-&gt;left, pre2, vin2);</span><br><span class="line">        node-&gt;right = <span class="built_in">reConstructBinaryTree</span>(node-&gt;right, pre3, vin3);</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ul>
</li>
</ul>
<h2 id="2-2-二叉树的下一个节点"><a href="#2-2-二叉树的下一个节点" class="headerlink" title="2.2 二叉树的下一个节点"></a>2.2 二叉树的下一个节点</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode* <span class="title">GetNext</span><span class="params">(TreeNode* pNode)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-3-打印二叉树"><a href="#2-3-打印二叉树" class="headerlink" title="2.3 打印二叉树"></a>2.3 打印二叉树</h2><h3 id="2-3-1-第一种方法"><a href="#2-3-1-第一种方法" class="headerlink" title="2.3.1 第一种方法"></a>2.3.1 第一种方法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;vector&lt;<span class="keyword">int</span>&gt; &gt; <span class="built_in">Print2</span>(TreeNode* pRoot) </span><br><span class="line">&#123;</span><br><span class="line">    stack&lt;TreeNode*&gt; sta;</span><br><span class="line">    queue&lt;TreeNode*&gt; q;</span><br><span class="line">    vector&lt;vector&lt;<span class="keyword">int</span>&gt;&gt;p;</span><br><span class="line">    <span class="keyword">if</span> (pRoot == <span class="literal">NULL</span>)<span class="keyword">return</span> p;</span><br><span class="line">    q.<span class="built_in">push</span>(pRoot);</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt;v;</span><br><span class="line">    <span class="keyword">int</span> m = <span class="number">1</span>;</span><br><span class="line">    m:</span><br><span class="line">    <span class="keyword">while</span> (q.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        TreeNode* a = q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        v.<span class="built_in">push_back</span>(a-&gt;val);</span><br><span class="line">        <span class="keyword">if</span> (m == <span class="number">1</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;left != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;left);</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;right != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;right);</span><br><span class="line">            m = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (a-&gt;right != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;right);</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (a-&gt;left != <span class="literal">NULL</span>)sta.<span class="built_in">push</span>(a-&gt;left);</span><br><span class="line">            m = <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    p.<span class="built_in">push_back</span>(v);</span><br><span class="line">    v.<span class="built_in">clear</span>();</span><br><span class="line">    <span class="keyword">if</span> (sta.<span class="built_in">size</span>() == <span class="number">0</span>)<span class="keyword">return</span> p;</span><br><span class="line">    <span class="keyword">while</span> (sta.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        q.<span class="built_in">push</span>(sta.<span class="built_in">top</span>());</span><br><span class="line">            sta.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">goto</span> m;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="2-3-2-第二种方法-顺序打印-栈存储每行信息"><a href="#2-3-2-第二种方法-顺序打印-栈存储每行信息" class="headerlink" title="2.3.2 第二种方法 顺序打印  栈存储每行信息"></a>2.3.2 第二种方法 顺序打印  栈存储每行信息</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">vector&lt;vector&lt;int&gt; &gt; Print(TreeNode* pRoot)</span><br><span class="line">&#123;</span><br><span class="line">    queue&lt;TreeNode*&gt; q, q2;</span><br><span class="line">    vector&lt;vector&lt;int&gt;&gt;p;</span><br><span class="line">    if (pRoot == NULL)return p;</span><br><span class="line">    q.push(pRoot);</span><br><span class="line">    vector&lt;int&gt;v;</span><br><span class="line">m:</span><br><span class="line">    while (q.size() &gt; 0)</span><br><span class="line">    &#123;</span><br><span class="line">        TreeNode* a = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        v.push_back(a-&gt;val);</span><br><span class="line">        if (a-&gt;left != NULL)q2.push(a-&gt;left);</span><br><span class="line">        if (a-&gt;right != NULL)q2.push(a-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    p.push_back(v);</span><br><span class="line">    v.clear();</span><br><span class="line">    if (q2.size() == 0)return p;</span><br><span class="line">    while (q2.size() &gt; 0)</span><br><span class="line">    &#123;</span><br><span class="line">        q.push(q2.front());</span><br><span class="line">        q2.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    goto m;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-4-先序遍历"><a href="#2-4-先序遍历" class="headerlink" title="2.4 先序遍历"></a>2.4 先序遍历</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">vector&lt;<span class="keyword">int</span>&gt; <span class="title">PreBinaryTree</span><span class="params">(TreeNode*root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    vector&lt;<span class="keyword">int</span>&gt; c;</span><br><span class="line">    stack&lt;TreeNode*&gt; s;</span><br><span class="line">    s.<span class="built_in">push</span>(root);</span><br><span class="line">    <span class="keyword">while</span> (s.<span class="built_in">size</span>() &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">auto</span> i = s.<span class="built_in">top</span>();</span><br><span class="line">        s.<span class="built_in">pop</span>();</span><br><span class="line">        c.<span class="built_in">push_back</span>(i-&gt;val);</span><br><span class="line">        <span class="keyword">if</span> (i-&gt;left)s.<span class="built_in">push</span>(i-&gt;left);</span><br><span class="line">        <span class="keyword">if</span> (i-&gt;right)s.<span class="built_in">push</span>(i-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-5-中序遍历"><a href="#2-5-中序遍历" class="headerlink" title="2.5 中序遍历"></a>2.5 中序遍历</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">MidBinaryTree</span><span class="params">(TreeNode* root)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="literal">nullptr</span>)<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (root-&gt;left)<span class="built_in">MidBinaryTree</span>(root-&gt;left);</span><br><span class="line">    c.<span class="built_in">push_back</span>(root);</span><br><span class="line">    <span class="keyword">if</span> (root-&gt;right)<span class="built_in">MidBinaryTree</span>(root-&gt;right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-6-请找出其中的第k小的结点"><a href="#2-6-请找出其中的第k小的结点" class="headerlink" title="2.6 请找出其中的第k小的结点"></a>2.6 请找出其中的第k小的结点</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">TreeNode* KthNode(TreeNode* pRoot, int k)</span><br><span class="line">&#123;</span><br><span class="line">    MidBinaryTree(pRoot);</span><br><span class="line">    return c[k - 1];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-7-删除二叉树"><a href="#2-7-删除二叉树" class="headerlink" title="2.7 删除二叉树"></a>2.7 删除二叉树</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Clear</span><span class="params">(TreeNode* pRoot)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (pRoot == <span class="literal">nullptr</span>)<span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (pRoot-&gt;left != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">        <span class="built_in">Clear</span>(pRoot-&gt;left); </span><br><span class="line">        <span class="keyword">delete</span> pRoot-&gt;left;</span><br><span class="line">        pRoot-&gt;left = <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (pRoot-&gt;right != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">        <span class="built_in">Clear</span>(pRoot-&gt;right);</span><br><span class="line">        <span class="keyword">delete</span> pRoot-&gt;right; </span><br><span class="line">        pRoot-&gt;right = <span class="literal">nullptr</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">delete</span> pRoot;</span><br><span class="line">    pRoot = <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1701%20%E7%AC%AC%E4%B8%83%E7%AB%A0%20%E6%A0%91%20%E4%BA%8C%E5%8F%89%E6%A0%91/" data-id="cl403sxs9003jf8vucjmt1hb6" data-title="二叉树" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  
    <article id="post-数据结构/2001 排序" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2001%20%E6%8E%92%E5%BA%8F/" class="article-date">
  <time class="dt-published" datetime="2021-12-12T06:46:54.000Z" itemprop="datePublished">2021-12-12</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="p-name article-title" href="/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2001%20%E6%8E%92%E5%BA%8F/">二叉树</a>
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h1 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h1><h2 id="知识图谱"><a href="#知识图谱" class="headerlink" title="知识图谱"></a>知识图谱</h2><p><img src="%2_D3I`7JCA{0@V421[B2Y6.png" alt="img"></p>
<h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><h3 id="排序定义"><a href="#排序定义" class="headerlink" title="排序定义"></a>排序定义</h3><h3 id="稳定性"><a href="#稳定性" class="headerlink" title="稳定性"></a>稳定性</h3><h3 id="衡量标准-时、空复杂度"><a href="#衡量标准-时、空复杂度" class="headerlink" title="衡量标准:时、空复杂度"></a>衡量标准:时、空复杂度</h3><h2 id="内部排序"><a href="#内部排序" class="headerlink" title="内部排序"></a>内部排序</h2><h3 id="插入徘序"><a href="#插入徘序" class="headerlink" title="插入徘序"></a>插入徘序</h3><h4 id="直接插入排序"><a href="#直接插入排序" class="headerlink" title="直接插入排序"></a>直接插入排序</h4><p>查找出L(i)在L[1……i-1]中的插入位置k<br>将L[k……i-1]中的所有元素全部后移一个位置<br>将L(i)复制到L(k)</p>
<h4 id="折半插入排序"><a href="#折半插入排序" class="headerlink" title="折半插入排序"></a>折半插入排序</h4><p>从上述算法中，不难看出折半括入排仅减小了比较元素的次数，约为O(nlog2n)，该比较次数与待排序表的初始状态无关，仅取决干表中的元素个数n;而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此,折半插入排序的时间复杂度仍为O(n2)。折半插入排序是一种稳定的排序方法。<br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">InsertSort</span><span class="params">(ElemType A[],<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function">    <span class="keyword">int</span> i, j,low,high, mid</span>;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">2</span>;i&lt;=n;i++)&#123;</span><br><span class="line">    <span class="comment">//依次将A[2]~A[n]插入前面的已排序序列</span></span><br><span class="line">        A[<span class="number">0</span>]=A[i];</span><br><span class="line">        <span class="comment">//将A[i]暂存到A[0]</span></span><br><span class="line">        low=<span class="number">1</span>;high=i<span class="number">-1</span>;</span><br><span class="line">        <span class="comment">//设置折半查找的范围</span></span><br><span class="line">        <span class="keyword">while</span>(low&lt;=high)&#123;</span><br><span class="line">            <span class="comment">//折半查找(默认递增有序)</span></span><br><span class="line">            mid=(low+high)/<span class="number">2</span>;</span><br><span class="line">            <span class="comment">//取中间点</span></span><br><span class="line">            <span class="keyword">if</span>(A[mid].key&gt;A[<span class="number">0</span>].key)high=mid<span class="number">-1</span>;</span><br><span class="line">            <span class="comment">//查找左半子表</span></span><br><span class="line">            <span class="keyword">else</span> low=mid+<span class="number">1</span></span><br><span class="line">            <span class="comment">//查找右半子表</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(j=i<span class="number">-1</span>;j&gt;=high+l;--j)</span><br><span class="line">            A[j+<span class="number">1</span>J=A[j];</span><br><span class="line">        <span class="comment">//统一后移元素，空出插入位置</span></span><br><span class="line">        A[high+<span class="number">1</span>]=A[<span class="number">0</span>];</span><br><span class="line">        <span class="comment">//插入操作</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h4 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h4><p>希尔排序的基本思想是:先将待排序表分割成若干形如 L[i, i+ d, i + 2d,…, i + kd]的“特殊”子表，分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。<br>希尔排序的排序过程如下:先取一个小于n的步长d,把表中的全部记录分成d组，所有距离为d的倍数的记录放在同一组中，在各组中进行直接插入排序;然后取第二个步长d,<d,重复上述过程，直到所取到的d, = 1，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是d =n/2，d+1=Ld/2],并且最后一个增量等于1.
空间效率：O(1)
时间效率：O(n^1.3) O(n^2)
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">shellSort</span> <span class="params">(ElemType A[],<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line"><span class="comment">//对顺序表做希尔抽八排了，伞早法N且按插入排序相比，做了以下修改:</span></span><br><span class="line"><span class="comment">//1.前后记录位置的增量是dk，不是1</span></span><br><span class="line"><span class="comment">//2.A[0]只是暂存单元，个是哨兵，当j&lt;=0时，插入位置已到</span></span><br><span class="line">    <span class="comment">//步长变化</span></span><br><span class="line">    <span class="keyword">for</span>(dk=n/<span class="number">2</span>;dk&gt;=l;dk=dk/<span class="number">2</span>)</span><br><span class="line">        <span class="keyword">for</span>(i=dk+<span class="number">1</span>;i&lt;=n;++i)</span><br><span class="line">            <span class="comment">//需将A[i]插入有序增量子表</span></span><br><span class="line">            <span class="keyword">if</span>(A[i].key&lt;A[i-dk].key)&#123;</span><br><span class="line">                <span class="comment">//暂存在A[0]</span></span><br><span class="line">                A[<span class="number">0</span>]=A[i];</span><br><span class="line">                <span class="comment">//记录后移,杳找插入的位置</span></span><br><span class="line">                <span class="keyword">for</span>(j=i-dk;j&gt;<span class="number">0</span>&amp;&amp;A[<span class="number">0</span>].key&lt;A[i].key;j-=dk)</span><br><span class="line">                    A[j+dk] =A[j];</span><br><span class="line">                <span class="comment">//插入</span></span><br><span class="line">                A[j+dk] =A[<span class="number">0</span>];</span><br><span class="line">            &#125;<span class="comment">//if</span></span><br></pre></td></tr></table></figure></p>
<h3 id="交换排序"><a href="#交换排序" class="headerlink" title="交换排序"></a>交换排序</h3><p> <img src="1.png" alt="1"><br><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Bubblesort</span><span class="params">(ElemType A[],<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line"><span class="comment">//用冒泡排序法将序列A中的元素按从小到大排列</span></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;n-l;i++)&#123;</span><br><span class="line"><span class="comment">//表示本趟冒泡具否发生交换的标志</span></span><br><span class="line">flag=<span class="literal">false</span>;</span><br><span class="line"><span class="comment">//一趟冒泡过程</span></span><br><span class="line"><span class="keyword">for</span>(j=n<span class="number">-1</span>;j&gt;i;j--)</span><br><span class="line"><span class="keyword">if</span>(A[j<span class="number">-1</span>].key&gt;A[j].key)&#123;</span><br><span class="line"><span class="built_in">swap</span>(A[j<span class="number">-1</span>],A[<span class="number">1</span>]);/交换</span><br><span class="line">flag=<span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">if</span>(flag==<span class="literal">false</span>)</span><br><span class="line"><span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br>冒泡排序算法的性能分析如下:<br>空间效率:仅使用了常数个辅助单元，因而空间复杂度为O(1)。<br>时间效率:当初始序列有序时，显然第一趟冒泡后flag依然为false （本题冒泡没有元素交换),从而直接跳出循环,比较次数n-1,移动次数为0.从而最好情况下的时间复杂度为O(n);当初始序列为逆序时，需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较，而且每次比较都必须移动元素3次来交换元素位置。这种情况下，</p>
<h4 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h4><h4 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h4><h3 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h3><h4 id="简单选择排序"><a href="#简单选择排序" class="headerlink" title="简单选择排序"></a>简单选择排序</h4><h4 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h4><h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><h3 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h3><h2 id="外部排序一—多路归并排序"><a href="#外部排序一—多路归并排序" class="headerlink" title="外部排序一—多路归并排序"></a>外部排序一—多路归并排序</h2>
      
    </div>
    <footer class="article-footer">
      <a data-url="https://goofyer.gitee.io/notes-on-computer-expertise/2021/12/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2001%20%E6%8E%92%E5%BA%8F/" data-id="cl403sxs9003lf8vu1zxd0kte" data-title="二叉树" class="article-share-link">Share</a>
      
      
      
    </footer>
  </div>
  
</article>



  


  <nav id="page-nav">
    
    <a class="extend prev" rel="prev" href="/notes-on-computer-expertise/page/13/">&laquo; Prev</a><a class="page-number" href="/notes-on-computer-expertise/">1</a><span class="space">&hellip;</span><a class="page-number" href="/notes-on-computer-expertise/page/12/">12</a><a class="page-number" href="/notes-on-computer-expertise/page/13/">13</a><span class="page-number current">14</span>
  </nav>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/C-%E5%B7%A5%E5%85%B7/">C#工具</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/C-%E5%B7%A5%E5%85%B7/">C++工具</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/Mysql/">Mysql</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/blender/">blender</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/manim/">manim</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/spring/">spring</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/vba%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/">vba基础操作</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E5%88%9B%E9%80%A0%E6%A8%A1%E5%BC%8F/">创造模式</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">操作系统</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">操作系统基础知识</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%BC%80%E5%8F%91/">操作系统开发</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E5%AD%A6/">数学</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/">数据结构基础知识</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%A8%A1%E6%9D%BF/">模板</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0/">深度学习</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%8B%B1%E8%AF%AD/">英语</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%99%9A%E5%B9%BB4/">虚幻4</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/">计算机组成原理</a></li><li class="category-list-item"><a class="category-list-link" href="/notes-on-computer-expertise/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BD%91%E7%BB%9C/">计算机网络</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/notes-on-computer-expertise/tags/C/" rel="tag">C++</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/notes-on-computer-expertise/tags/C/" style="font-size: 10px;">C++</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/05/">May 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/03/">March 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/02/">February 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2022/01/">January 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/notes-on-computer-expertise/archives/2021/12/">December 2021</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/31/vue/%E5%89%8D%E7%AB%AF%E6%A1%86%E6%9E%B6%E9%AA%8C%E8%AF%81%E7%A0%81%E6%97%A0%E6%B3%95%E6%98%BE%E7%A4%BA/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/26/%E6%95%B0%E6%8D%AE%E5%BA%93/navicat%E5%AE%89%E8%A3%85/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/25/%E8%99%9A%E5%B9%BB4%E5%BC%95%E6%93%8E%E5%BC%80%E5%8F%91/%E8%99%9A%E5%B9%BB%E5%9B%9B%20mod%E5%88%B6%E4%BD%9C/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/23/python/python%E6%89%B9%E9%87%8F%E7%94%9F%E6%88%90%E6%95%B0%E6%8D%AE/">(no title)</a>
          </li>
        
          <li>
            <a href="/notes-on-computer-expertise/2022/05/23/vba%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C%E7%AC%94%E8%AE%B0/EXCEL%E5%9F%BA%E7%A1%80%E6%95%99%E7%A8%8B/">(no title)</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2022 John Doe<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/notes-on-computer-expertise/" class="mobile-nav-link">Home</a>
  
    <a href="/notes-on-computer-expertise/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/notes-on-computer-expertise/js/jquery-3.4.1.min.js"></script>



  
<script src="/notes-on-computer-expertise/fancybox/jquery.fancybox.min.js"></script>




<script src="/notes-on-computer-expertise/js/script.js"></script>





  </div>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>
</html>